Research On Integer Programming Based On Estimation Of Distribution Algorithms

Estimation of Distribution Algorithms(EDAs)were introduced by M(?)hlenbein and Paaβin 1996,which have attracted more and more researchers' attention for their outstanding abilities of searching global optimal solutions.As far,EDAs have already been successfully applied to many areas such as multi-objective optimization, automotive gears mechanical structure,feature selection,inaccurate graphics matching,cancer classification,characteristics of biological information extraction, military antenna design optimization and so on.The work of this thesis focuses on the improvement and application of EDAs. The main contributions of this thesis are as follows:EDAs with mutation operation are presented in this thesis,which add mutation operation to traditional EDAs.Because traditional EDAs sample new solutions from a probability model which characterized the distribution of promising solutions in the search space at each generation.The location information of solutions found so far can not directly used for generating offspring in most existing EDAs.The proposed method generates offspring through combination of global statistical information and the location information of solutions found so far.So the above proposed method improves the performance of EDAs.EDAs with mutation are used to solve nonlinear integer programming problems. To prove the effectiveness of the proposed algorithms,it is tested on three nonlinear integer programming problems.The experimental results show that the proposed algorithm can solve NIP successively.EDAs with mutation are applied to solve the maximum clique problem,which are compared with the heuristic genetic algorithm of Marchiori and MIMIC algorithm. Experimental results show that the proposed algorithm outperforms the heuristic genetic algorithm of Marchiori and MIMIC algorithm on DIMACS benchmark graphs.EDAs based on Latin Hypercube Designs are proposed in this thesis.The idea of Design of Experiments is introduced to traditional EDAs,and EDAs based on Latin Hypercube Designs are proposed.Compared with former algorithms,the new algorithm can get better initial generations.The experimental results show that the EDAs based on Latin Hypercube Designs outperform the traditional EDAs.