A Genetic Algorithm Research For Solving Constrained Optimization Problems

Many practical problems can be formulated as constrained optimization problems and the optimal solutions are often located on or close to the boundary of the feasible region. But traditional approaches are not always useful to solve these kinds of problems. So, this paper proposes an improved genetic algorithm based on the boundary simulation method. Where, the boundary point set is generated by the modified boundary simulation method:The first step is to generate feasible points. For some simple constrained problems, the random generation method will be more efficient than any other evolutionary algorithms. But, it is difficult in dealing with complex constraints. In order to generate the feasible point set efficiently with genetic algorithm for any problems, the paper modifies the algorithm convergence conditions appropriately;The second step is to generate infeasible points. Based on the result of the first step, an outer space is constructed which envelops the search space and the feasible region is located as much as possible in the center. Then infeasible points can be generated from boundary of the outer space;The final step is to calculate the boundary points of the feasible region between the feasible and infeasible points with the improved backward binary search method. When enough of the points are found, the largest boundary of the feasible region can be simulated approximately.Then the improved genetic algorithm generates chaos initial population from the boundary point set directly. Compared with the initial population generated randomly, the diversity of the former is more stable. Additionally, a simple elitist strategy and the well-known fitness proportionate selection operator are adopted to avoid the loss of the best individual. And the infeasible ones produced by the crossover and mutation operators are repaired with the binary search method. Thus, all the individuals of each generation will be feasible. According to the logical subsequence, this paper combines the boundary simulation method with the improved genetic algorithm and evaluates the hybrid algorithm’s convergence and time complexity. At last, the method is used to solve test problems and the results indicate its better global convergence compared with other studies.