| Combinatorial optimization problems exist in many practical problems such as communication network design problem, x- ray crystal problem, VISI problem, and irrigation ditch design problem. Most such problems are NP-hard, and we can apply exact optimization algorithms only to small instances of them. For larger instances, we turn to heuristic technique, including genetic algorithms (GAs). In recent years, Genetic algorithms have been widely used in many fields to solve these problems, such as minimum spanning trees problems, traveling salesman problems, and so on.Firstly, the TSP is studied, and a novel genetic approach for TSP without fixed starting point and endpoint is proposed. To make the propose algorithm effectively, the solution representation is simplified first. As a result, a simplified encoding scheme is presented, and an efficient decoding scheme is designed. Then based on the specific encoding scheme, the efficient crossover and mutation operators are proposed. It can always generate valid tour. In order to enhance its ability of exploration, a local search scheme is integrated into the crossover operator. Based on these, a novel and effective genetic algorithm for TSP is presented and its convergence to global optimal solution is proved. Finally, the simulation results show the effectiveness of the proposed algorithm.Secondly, a novel Genetic algorithm for the degree constrained minimum spanning tree problem is presented. To generate feasible initial population consist of a set of random spanning trees, the idea of Dijkstra algorithm and a specific encoding scheme are use to design a new algorithm for producing feasible initial population. Based on this encoding scheme, a crossover and a mutation operators are proposed, which have the ability to transfer the good genes (edges) of parents to their offspring. The global convergence of the algorithm with probability one is proved .The numerical experiments demonstrate the efficiency of the algorithm.
|
PDF Full Text Request