Genetic Algorithm For Solving Linear Bi-level Programming With Interval Coefficients

Bi-level programming is a kind of hierarchical optimization problem, and has beenwidely applied in real world. A feature of the problem is that the constraint region of anoptimization problem involves another optimization problem. As a result, bi-levelprogramming problems are computationally complex. Since the data measurement,modeling, dynamic data and other reasons, the coefficient of the optimization problem isoften uncertain. The problem with uncertainty is called uncertain optimization problem.In uncertain optimization problems, interval coefficient optimization is a hot topic inrecent years, which is characterized by interval coefficients. Due to the complexity of theproblem, there are few approaches to solve bi-level programming problems with intervalcoefficients. Some algorithms, such as k-th best algorithm, always need a large amountof computation due to too many vertices when large-scale problems are solved. In thisthesis, the genetic algorithm is taken as a framework to deal with two types of linearbi-level programming with interval coefficients, and the corresponding algorithms arepresented.1. For linear bi-level programming problems with interval coefficients in the upperlevel objective, a genetic algorithm is proposed by using a double fitness functionevaluation technique, which is characterized by simultaneously obtaining the bestoptimal solution as well as the worst one in one run of the genetic algorithm. Firstly,individuals are encoded by using the vertices of the constraint region, and a doublefitness is constructed by the upper and lower bounds of the upper level objectivecoefficients. Secondly, fitness functions are used to sort all individuals in populations.According to the order, the feasibility of individual is checked, one by one, until afeasible individual is found. Finally, the feasible individual is updated in executing algorithm. The simulation results on computational examples show that the proposedalgorithm is feasible and efficient.2. For linear bi-level programming problems with interval coefficients in the upperand low level objectives, a genetic algorithm is proposed to find the best optimalobjective function. Firstly, each individual is encoded by selecting lower level constraints.Some several constraints are chosen as equalities by which the lower level variables areexpressed as functions of the upper level variables. Secondly, in the original problem, thelower level variables are replaced by these functions. As a result, the problem becomes alinear program only involving upper level variables. Further, the linear program is solvedto get a point. Finally, the feasibility of the point is checked by using the duality theorem.If the point is feasible, then the optimal value of the linear program is taken as the fitnessof the individual, and the best individual is updated at each iteration of the algorithm.