Genetic Algorithms For Space Allocation Problems

Evolutionary algorithms are new kinds of modern optimization algorithms that are inspired by principle of nature evolution. Compared with the traditional optimization algorithm, the evolutionary algorithms require little knowledge about problems considered, and they are easy to implement and are of inherently parallel search ability. Therefore, the evolutionary algorithms have been successfully applied to various fields, especially to some complex, large scale, nonlinear and non-differentiable optimization problems.Firstly, a new model for airport gate assignment problem (AGAP) is developed based on the Model which is proposed by H.Ding, where each of flights can only be assigned to some gates, and the objective is to minimize the distance the passengers walk or the connection times. To solve this problem, a genetic algorithm is proposed based on a new encoding scheme called (use another name instead of AGAP), a novel crossover and mutation operators. The solutions generated by the proposed crossover and mutation operators are always feasible,and the mutation operator not only has strong exploration ability, but also can handle the constraints effectively. Moreover, the convergence of the proposed algorithm is proved. The simulations indicate the proposed genetic algorithm can find optimal solution quickly.Secondly, a hybrid genetic algorithm for the shelf space allocation is presented based on Yang'model which was proposed in 1999, where the algorithm integrated the simulated annealing and a local research method into a genetic algorithm. In the encoding, a matrix is adopted to represent a solution (i.e., a space-allocation scheme), where the element of the i th row and the k th column represents the amount of product i on shelf k. Then crossover and mutation operators are designed. Moreover, a threshold valueζbased on structure of phenotype and its fitness is defined to generate good enough initial population. Compare to other heuristic methods, the numerical experiments demonstrate the proposed algorithm is very efficient in searching the solution space and has a rapid speed.Thirdly, a bi-objective model for the shelf space allocation problem is proposed based on improving the existing work, and a hybrid genetic algorithm for this model is designed. Moreover, three local methods which can improve the feasible solution from different directions are designed according to the specific features of the problem, and they are combined into the genetic algorithm to increase its search ability. A number of simulated results show the efficiency of the proposed algorithms.