Genetic Algorithms In Graph Theory And Optimization

Many optimization problems are NP-complete problems. Such problems are the fundamental problems in scientific computation and engineering design. One of the main research fields is to incorporate the conventional heuristics into genetic algorithms to construct a more competitive genetic algorithm for these difficult-to- solve optimization problems. We conduct a deeper research on the basic theory of genetic algorithm and present some effective algorithms on these difficult problems. The evolutionary process of the probability density of the population is analyzed in a simple way. The recursive formulas of the probability density of the population in continuous space are derived in a simple way. The basic properties associated with selection and mutation are analyzed. Sufficient conditions for monotonous increase of the average fitness converging to the global optimum in continuous space and evolutionary process converging to the global optimum in discrete space are presented. These conclusions provide a basis in theory in some extent for the adaptive mutation operator and the convergence of genetic algorithm to the global optimal solution. Hybrid genetic algorithms for the vertex cover problems in which scan-repair and local improvement techniques are used for local optimization are presented. With the hybrid approach, local optimization is applied to each newly generated offspring to move it to a local optimum before injecting it into the population. Genetic algorithms are used to perform global exploration among a population, while heuristics methods are used to perform local exploitation around the chromosome. The experimental results indicate that hybrid genetic algorithms can obtain solutions of excellent quality of problem instances with different size. The results are compared among the three algorithms (GA, SRGA, SLGA). The pure genetic algorithms are outperformed by the neighborhood search heuristics procedures combined with genetic algorithms. 4 iv ABSTRACT ? New genetic algorithms for 0/1 knapsack are addressed which extend the traditional algorithm. The algorithm presented is effective for the larger size of problems. ? Graph coloring is a typical NP-complete problem. On the comprehensive study of some properties of proper k-vertex-coloring, k-edge-coloring, and total-coloring of a graph, a new hybrid genetic algorithm for graph coloring is presented. This new method involves hybridizing conventional heuristics such as greedy into genetic algorithm where possible and uses heuristics to decode chromosomes to color. With the hybrid approach, genetic algorithms are used to perform global exploration among population while heuristics methods are used to perform local exploitation around chromosomes. The experimental results show that it can obtain solutions of excellent quality for a graph. It outperforms both pure heuristics procedure and tabu search hybrid genetic algorithm. ? A genetic algorithm for the Flow-shop problem is presented. The comparison of genetic algorithm with Johnson抯 results is given for six-job two-machine problem. The genetic algorithm can obta...