Khulna University of Engineering & Technology

ABSTRACT : Solving a set of simultaneous linear equations is a fundamental problem that occurs in diverse applications. For solving large sets of linear equations, iterative methods are preferred over other methods specially when the coefficient matrix of the linear system is sparse. The rate of convergence of iterative (Jacobi & Gauss-Seidel) methods is increased by using successive relaxation (SR) technique. But SR technique is very sensitive to relaxation factor, . Recently, hybridization of evolutionary computation techniques with classical Gauss-Seidel-based SR method has successfully been used to solve large set of linear equations in which relaxation factors are self-adapted. Under this paradigm, this research work has developed a new class of hybrid evolutionary algorithms for solving system of linear equations. The first algorithm is the Jacobi-Based Uniform Adaptive (JBUA) hybrid algorithm, which has been developed within the framework of contemporary Gauss-Seidel-Based Uniform Adaptive (GSBUA) hybrid algorithm, and classical Jacobi method. The proposed JBUA hybrid algorithm can be implemented, inherently, in parallel processing environment efficiently whereas GSBUA hybrid algorithm cannot be implemented in parallel processing environment efficiently. The second algorithm is the Gauss-Seidel-Based Time-Variant Adaptive (GSBTVA) hybrid algorithm that has been developed within the framework of contemporary GSBUA hybrid algorithm and time-variant adaptive technique. In this algorithm two new time-variant adaptive operators have been introduced based on some observed biological evidences. The third algorithm is the Jacobi-Based Time-Variant Adaptive (JBTVA) hybrid algorithm that has been developed within the framework of GSBTVA and JBUA hybrid algorithms. This proposed JBTVA algorithm also can be implemented, inherently, in parallel processing environment efficiently. All the proposed hybrid algorithms have been tested on some test problems and compared with other hybrid evolutionary algorithms and classical iterative methods. Also the validity of the rapid convergence of the proposed algorithms are proved theoretically. The proposed hybrid algorithms outperform the contemporary GSBUA hybrid algorithm as well as classical iterative methods in terms of convergence speed and effectiveness.

Abstract: Maximin Distance Problems are belong to distance geometry problems. Maximin distance using as an optimal criterion are relatively new tools for global optimization problems. Owing to their large applicability, recently a lot of attention has been paid to maximin distance geometry problems. In this thesis we mainly deal with two problems -- experimental design and packing problems.In the field of experimental design problems we consider maximin Latin Hypercube Designs (LHDs). In the field of packing problems we consider those of packing $n$ equal or unequal circles in a circular container with minimum radius. Both problems can be formulated as optimization ones. The former is a combinatorialproblem, while the latter is a continuous one. We propose heuristic approaches to tackle these problems. These are Iterated Local Search (ILS) heuristics for maximin LHDs, and Basin Hopping (BH) heuristics for packing problems. Actually,ILS and BH approaches have strong similarities and could be described within an unified framework. However,following the literature, where ILS approaches are mainly applied to combinatorial problems, while BH approaches are mainly applied to continuous problems, we will keep them apart. In order to deal with maximin LHDs, we propose two ILS variants, corresponding to two distinct optimality criteria which are employed to drive the searchamong LHDs. Extensive experiments are performed for the investigation of the strengths and weaknesses of the algorithms.A remarkable finding is that the most efficient method, though time consuming, performs a non monotonic search, driven by an appropriate objective function, within the space of LHDs. The proposed approaches are extensively compared with the existing ones in the literature, and many improved results with respect to best known ones, are obtained. In particular, the proposed methods seem to outperform the existing ones when the dimension of the design points increases. Finally, we also discuss about the time complexity of the algorithms: by mixing theoretical resultswith experimental ones, we derive an empirical formula for each ILS variant, returning the expected run time as a function of the number of design points and of their dimension. To deal with the problem of packing {\em equal} circles in a circular container with minimum radius,we propose a variant of BH, namely Monotonic BH (MBH) and its population based counterpart, Population BH (PBH). Extensive computational experiments are performed both to analyze the problem at hand, and to choose in an appropriate way the parameter values for the proposed methods. Different improvements with respect to the best results reported in the literature are detected.The problem of packing {\em unequal} circles in a circular container with minimum radius is also attacked with the MBH and PBH approaches, but some components of these approaches are adapted in order to fully exploit the peculiarities of the problem with unequal circles (in particular, its combinatorial nature due to the different radii of the circles). Again extensive computational experiments are performed and improvements with respect to the existing literature are detected.