论文部分内容阅读
20世纪60年代，美国Michigan大学的J.Holland教授首先提出了遗传算法(Genetic Algorithm，缩写为GA)，它是模拟达尔文的遗传选择和优胜劣汰的生物进化过程的计算模型。经过三十多年的发展，无论在算法的改进方面，还是理论以及应用研究方面，都已取得了很大的进步和成功。但是遗传算法中仍然存在许多问题，如建筑块假设、早熟收敛和进化时间长等问题。 思维进化计算(Mind Evolutionary Computation，简称为MEC)是孙承意教授于1998年提出的一种新的进化计算(Evolutionary Computation，简称为EC)方法。它是根据对GA存在问题的思考以及对人类思维进步的分析，模仿人类社会中存在的趋同和异化现象提出来的。研究表明：MEC的计算效率和收敛性能比标准GA及其它进化算法一般要高50％以上，说明MEC是一种高效的算法。并且MEC在求解数值优化问题(包括多峰优化、多目标优化等)和非数值优化问题(包括TSP、Job shop、系统动态建模等)中，都取得了非常好的效果。研究表明MEC已经形成了初步完整的学术体系。 最大团问题(Maximum Clique Problem，简称MCP)是图论中的非常经典的组合优化问题。最大团问题是一个NP完全(NP-complete)问题。最大团问题在实践中有很广泛的应用。太原理工大学硕士研究生学位论文 本文提出采用思维进化计算(Mind EvolutionaryCo娜utation，MEC)求解最大团问题(Maximum Clique Problem，MCP)的一个启发式算法—MCP一MECI。解决了采用MEC求解最大团问题时个体与子群体的构造，个体的评价，趋同与异化操作的构成等问题。采用DIMACS(Diserete MathematicS&仆eoretieal eo哪uter seience)组织所提供的基准图对MCP一MECI算法进行了测试，并与当前求解最大团问题的最好方法，甩S(Reaetive Loeal seareh)算法和HoA(heuristie genetiealgorithm)算法，进行了比较。实验结果表明，McP一MEcl的性能优于HGA，与RLS相当，是当前求解最大团问题的最好的启发式算法之一。