共同进化计算及其应用研究

Coevolution among different species is a general type of phenomena characteristic of biologic evolution in nature, which can be simulated to improve the efficiency and adapatability of evolutionary computations. The computational models of coevolution and their applications in complex optimization problems have been studied in this project. Main researches include: problem decomposition-based scalable macro-evolutionary algorithms, the coevolutionary computation model of genetic epistasis, the coevolutionsry computation models for task matching and scheduling problems, evolutionary decision-making techniques based on candidates ranking, evolutionary approximation technique of multi-dimensional functions, multi-objective optimization and decision-making techniques based on coevolutionary computations, evolutionary algorithms of magic squares, the principle of digital lock based on random magic square, two-way authentication and job key agreement based on random magic square, fast and exact algorithms of quadratic knapsack problems, genetic algorithms for general assignment problem. For the macro-evolutionary algorithm using divide-and-conquer approach, the increase exponent of the density of over-average fitness individuals in a population is greater than that of standard evolutionary algorithm, and increases exponentially with the number of grains decomposed. The numerical experiments consist well with this theoretical result. The macro-evolutionary algorithm can overcome the difficulty associated with dimensionality and reduce as much as possible the difficulty due to intensive epistasis; it is thus scalable and useful in engineering. The efficiency of coevolutionary algorithm for the scheduling problems with independent multi-tasks is greater than that of conventional genetic algorithms. The branch-and-bound algorithm with Lagrangian relaxation method to compute the upper bounds was proposed to solve quadratic knapsack problem (QKP), in which the computational efficiency decreases with the density of positive profits, this density susceptibility is analyzed in this paper. An ultimate reason is given that there may not exist an optimal Lagrangian multiplier matrix for QKPs with non-positive profits, so that the optimal solution to the Lagrangian relaxed problem can meet its dualized equality constraints, resulting in an upper bounding of low precision. The profit swindling approach proposed by us can eliminate the profit density's effects on computational efficiency and greatly exceed the exact QKP algorithms in overall efficiency, but without exactness reduction. The method of two-way authentication and key agreement is patent-pending and will have a near future of wide applications in network information security.

基于对单种群进化计算收敛性与多样度矛盾的分析，本课题旨在研究多因子且无一致适应值图景下共同进化计算的理论与应用。主要内容包括共同进化环境适应值评估、合作与竞争机制、异构进化、层次进化、共同进化模型及其并行计算模型等，并把共同进化计算理论用于金融股市经济学建模、细胞自动机反问题求解以及多目标优化与决策的自然平衡等问题。