The Research On Adaptive Memetic Algorithm For Solving Discrete Constrained Optimization Problem

In the field of computer application,many practical engineering problems can be modeled as Discrete Constrained Optimization Problem,including production planning problem,scheduling and time-tabling problem,multi-dimensional knapsack problem and protein structure prediction problem and so on.For Discrete Constrained Optimization Problem,the search space is discrete,severely constrained and multi-optimal.Therefore,developing the appropriate optimization al-gorithm to solve the Discrete Constrained Optimization problem has always been the focus of research work.This paper mainly researches and designs adaptive memetic algorithms for solving Discrete Constrained Optimization Problem,including Set Covering Problem(SCP)and the Single-Source Capacitated Facility Location Problem(SSCFLP).In this work,we design a hybrid encoded adaptive memetic algorithm for solving SCP.Firstly,we model the SCP instance as row and column covering problem of 0-1 matrix.Then a genetic algorithm framework is applied,and a local search strategy com-bined with mutation operator is used to solve SCP.The main contributions of this work include the following four aspects:(1)We introduce a hybrid encoding approach to en-code two genetic segments for each individual chromosome,in which the first segment encodes a solution,and the second segment encodes the row weighting information.The weight of row reflects the possibility of row being covered in next iteration,and will be updated as the evolution goes.(2)Based on the row weighting,a adjustment mechanism of column weight is proposed,in which column weight is calculated as heuristic information.Then,a local search strategy combined with mutation operator is used to improve the solution quality.(3)To avoid dealing with a large number of infeasi-ble solutions brought by traditional crossover operation,a fragment-crossover operator on the meme is proposed to make the meme participate in evolution,which increases the internal information exchange and avoids being stuck into local optimum.(4)Ex-perimental results on the benchmark instances from Beasley's OR Library for unicost SCP and non-unicost SCP show that the proposed hybrid encoded memetic algorithm produces competitive solutions in comparison with other meta-heuristics.Furthermore,a vability evolution adaptive memetic algorithm is also designed for SSCFLP.The objective function is considered as a new constraint in the evolution pro-cess,which is tapered off until finding the optimal value.Then,a threshold variable? is defined and adjusted adaptively.The individuals outside the threshold are elimi-nated.Besides,for the rest individuals,a stochastic local search operation is performed to improve individual quality.To maintain the size of population,we design a Greedy Partition Crossover(GPX)to generate offspring.The main contributions of this work in-clude the following four aspects:(1)To avoid the huge amount of computation brought by executing local search strategy for each offspring,the Viability Evolution strategy is used to replace the classical selection operation in the genetic algorithm.(2)We main-tain a score term between each facility and each customer,which is based on fixed setup cost and transport cost.And the score item is updated as evolution process goes,which is used to designed a stochastic local search method to improve individual quality.(3)In order to avoid the redundancy and conflict issues caused by the simple crossover oper-ator,we designed Greedy Partition Crossover to generate new individuals.(4)Through the test on the OR-Library and Yang instances set,the experimental results show that our algorithm can solve the large scale problem of SSCFLP more efficiently than Cut-and-Solve algorithm.