【作者】 黄樟灿；

【导师】 康立山；

【作者基本信息】 武汉大学 ， 计算机软件与理论， 2004， 博士

【摘要】 最优化理论是数学的一个分支,研究的是某些数学问题的最优解,即对给出的实际问题,从众多候选方案中找到最优方案。它具有高度的应用性和技术性的特点。 现在,解线性规划、非线性规划、随机规划、多目标规划、几何规划、整数规划等各种问题的最优化理论研究迅速发展,新的方法不断出现,实际应用日益广泛。这样的算法使用的是确定性的搜索方法,一个搜索点到另一个搜索点的转移有确定的转移关系,这种确定性使得算法的搜索具有定向性,从而有很快的收敛速度但很难达到问题的全局最优解,而且数值稳定性不好。作为解决复杂、困难的全局优化问题的演化计算也得到迅速的发展。从演化计算产生至今,算法设计一直是它的核心,也是人们所关注和研究的重点。这方面的研究始终围绕两个主题:一是扩大可应用领域;二是使之更加有效。前者旨在设计和发现有效的EC搜索策略,以解决过去不能解决或不能有效解决的问题;后者着重于修正和改进已有算法,使之更加有效。 论文围绕EC算法设计的两个主题,结合EC的特点,利用传统算法的本质特性,对EC的搜索策略进行了深入的研究,并取得了一系列成果。全文分为三大部分。 第一部分为最优化理论、演化计算基础理论的分析总结和演化计算搜索策略的研究。具体包括:分析了传统算法的搜索策略,总结了它们的本质特性。针对演化计算产生新解无序的矛盾,提出了基于相似性的邻域搜索策略。利用邻域搜索,可以方便地建立自适应的新解产生机制,在统一的框架下处理不同的优化问题。针对算法设计中存在的搜索效果和效率平衡问题,提出了利用适应值对个体进行分级的搜索策略。通过对个体的分级,可以区分个体在搜索过程中的职能:优秀的个体进行局部极小值的开采;其它的个体进行搜索空间的探索,以发现新的局部极小值,从而达到搜索效果和效率的平衡。针对演化计算搜索效率较差的问题,结合传统算法和数值分析的加速思想,提出了用父代个体信息的组合进行加速的搜索策略;针对小同的使用坏境,设计了三个加速算子,通过加速算子的使用,算法的搜索效率得到提高。为了提高收敛速度,结合模拟退火的思想,设计了邻域收缩技术。通过邻域收缩,算法的搜索速度明显提高。根据上述的搜索策略,结合演化计算的特点,提出了一个新的算法框架SFEC(Similarity Frame of Evolutionary Computation)。 第二部分为算法框架的性能测试。对函数优化、整数规划、多目标优化、TSP问题,根据它们各自的特点,利用算法框架设计了具体的算法。关于函数优化问题,更多还原

【Abstract】 The optimal theory is a mathematical branch, the research focuses on some mathematical problems’ optimal solutions, namely to the actual problem which produces, finding the optimal solution from the multitudinous candidate solutions. It has highly application and technical characteristics.Nowadays, research in linear programming (LP), non-linear programming (NLP), random programming (RP), multi-objective programming, integer programming (IP) has grown tremendously. New methods continuously emerged, and the practical application widely used. Evolutionary computation which is used to solve complex , difficult global optimal problems has rapid progress. As evolutionary computation developed, algorithm design is its key as well as the emphases people focus on and research in. The research revolves two subjects: First, to expanse the application domain; Next, to cause it more effective. The former is for the goal of designing and discovering effective EC search strategies, solving the problem the past unable to solve or cannot to be solved effectively; The latter is to revise and improve emphatically the algorithm, causes it to be more effective.The dissertation revolves the two subjects of EC algorithm designing, unifies the characteristics of EC, uses essential characteristics of traditional algorithms, has conducted the thorough research to the EC search strategies, and has yielded a series of satisfactory results. The dissertation consists of three major parts.The first part is the optimal theory, basic EC theory analysis summary and the research on EC search strategies. It deals with traditional algorithm search strategy, summarizes their essential characteristics. As to the conflict of EC generating new individuals randomly, we proposed a neighborhood search strategy based on similarity. Neighborhood search brings the ability to self-adaptively generate new individuals easily as well as deal with all kinds of optimization problem in the uniform frame. Aiming at balancing search results and search speed, we proposed a search strategy to classify the individuals by their fitness. By individuals classification to differentiate respective function in search process, that’s the excellent individual to explore the local optimal solution and others to explore the search domain to find new local optimal solution. Aiming at EC bad efficiency, uniting traditional algorithm and numerical analysis’s speed up thought, we proposed a speed up search strategy by combining parent population’ information. Aiming at different conditions, we design 3 speed-up operators and apply them in the algorithm. The search efficiency is highly improved. To improve the convergence speed, with simulate annealing, we design a neighborhood contractive technical. The search speed is enhanced. According to search strategies mentioned above, united EC characteristics, we proposed a new algorithm framework SFEC (SimilarityFrame of Evolutionary Computation).The second part is to check the ability of the algorithm frame. As to functions optimization, integer programming, multi-objective optimization, TSP with their special characteristics, the respective algorithm designed under the algorithm frame. In the case of functions optimization, ten normal test functions are adopted. The results show that algorithm can not only find 9 test functions, bump function under 30 dimensions global optimal solutions also has quickly speed and strong numerical reliability. As to the bump function from 30 to 100 dimensions, the algorithm can find the global optimal solution in short time but the numerical reliability is not so ideal. As to bump function above 150 dimensions, the algorithm is hard to find its global optimal solution. In the case of integer programming, using 2 test functions the algorithm find the global optimal result in very short time. In the case of multi-object optimization, the algorithm solves the 5 classical test problems successfully. In the case of combination problem, the author test TSP, which turns out in low dimension satisfactory results obtained but in high dimension deep further research should be carried.The third part is the application. SFEC has a potential for a wide range of application. We apply the algorithm into typical problems. We use network topology design and self-adaptive management of distributed information systems as the examples in network optimization, to build and solve the mathematical models. As for designing network topology, we take common network reliability and its cost as object functions to build the mathematical model, and as for ATM network, the burden and its cost are used to build the model. As for self-adaptive management of distributed information systems, we introduce 3-dimensional variable to build the mathematical model on file content. These are all multi-objective optimization problems. We use the SFEC to solve them by weight allocation. The numerical experimental results indicated the new algorithm can solve the network optimal problems effectively and the mathematical model can reflect the features of the system, also satisfy optimal characteristics.At last, the research results in the dissertation are summarized. We suggest that more research work in this area should be done, and predict bright prospect of future research.更多还原