Genetic Algorithms For Solving Special Bi-level Programming Problem

Bi-level programming problem, briefly denoted by BLPP, has been widely used,and the research on algorithms for BLPP is of real significance. So much attention hasbeen paid to this area in recent years. Bi-level programming problems (BLPPs) arenon-convex optimization problems with hierarchical structure. It is very difficult todetermine its solution of BLPP because of its inherent non-convexity andnon-differentiability. In particular, it is more difficult to get the global optimal solutionof nonlinear BLPP. Genetic algorithm, briefly denoted by GA, is a new kind of effectivealgorithm for very complex nonlinear programming. It is not restricted by functionsinvolving requiring differentiability, convexity continuation and so on. It has someadvantages such as global search ability, implicit parallelism, robustness, simpleoperation and so on.In this paper, we study the difficulty of bi-level programming and goodperformance of genetic algorithm. Genetic algorithms are applied to solve two kinds ofbi-level programming. One kind is the lower for convex quadratic programming bi-levelprogramming, and the other kind is a gray bi-level linear programming.Firstly, for a class of convex quadratic programming bi-level programming, theoptimal solution of the lower-level problem is represented by the upper-level variablesor Lagrange multipliers. The lower-level variables are a function of upper-levelvariables. Then the bi-level programming program can be transformed into asingle-level optimization program containing the upper-level variables or Lagrangemultipliers through replacing the lower-level variables by this function. The method istaken as an improved mutation operator and a local search operator to improve solutionaccuracy, and the hybrid GA is applied. The theoretic analysis and the simulation resultson many numerical examples show that the proposed algorithm is effective and can findhigh quality solutions.Secondly, we study the gray bi-level linear programming (GBLP). In this paper,the positioned interval and a new method of calculating the pleased degree are putforward. The properties and solution are studied. According to the properties of GBLP,we improve the methods of the particle population’s initialization and the fitnessvalue’s calculation. An initial judgment of the GBLP’s solutions is made, and a new genetic algorithm is designed. At last, a numerical example is given to show that thefeasibility of the algorithm.