摘 要

这篇论文简述了启发类优化算法与化学反应优化算(Chemical Reaction Optimization, 简称CRO )的背景，并简单分析了这些算法的原理，化学反应优化算法受到化学反应中分子之间相互作用的规则以寻求势能面中最低势能原理的启发，采用四种基本反应，遵循热力学第一、第二定律，具有简单通用、鲁棒性强、自学习、自组织、自适应等特点。据此，我们尝试用该算法去解决最小顶点覆盖问题.

首先根据最小顶点覆盖问题的无向图邻接矩阵，设置使用化学反应优化算法过程中需要用到的分子编码和适应度函数，同时针对最小顶点覆盖问题所具有的特点对算法过程中的四个重要参数进行设置。最后根据化学反应中生成物势能会趋于最小的特点在解空间中进行搜索。

根据测试结果，在求解最小顶点覆盖问题中，化学反应优化算法在求解速度和精确度方面表现的非常好。

关键词：启发类优化算法；最小顶点覆盖问题；化学反应优化算法；无向图

Abstract

This paper introduces the bionic optimization algorithm and chemical reaction optimization with simple analysis of their theory. Chemical Reaction Optimization (CRO) is proposed for the minimum vertex cover problem in this paper in the same time. According to the undirected graph adjacency matrix, chemical reactions molecular coding is designed. The four important operators are designed creatively according to the characteristics of problem. The optimal solution is searched in the solution space by simulating the process of chemical reaction in which potential energy gradually stabilize. The experimental result proves that the new method is effective for solving minimum vertex cover problem of undirected graph，and it performs remarkably better than the general genetic algorithm in solving speed．

Key words: vertex cover problem; undirected graph; the bionic optimization algorithm; chemical reaction optimization;

目 录

摘 要 I

Abstract II

第1章 绪论 1

1.1 研究的目的及意义 1

1.2 研究背景 1

1.3 研究现状 3

1.4 研究内容 3

第2章 启发类优化算法简述 5

2.1 引言 5

2.2几种启发类算法的基本思想 5

2.2.1 遗传算法 5

2.2.2 蚁群算法 7

2.2.3 混合蛙跳算法 8

2.3算法分析 8

第3章 化学反应优化算法理论及浅析 11

第4章 化学反应优化算法的实际应用 15

4.1 引言 15

4.2问题描述 15

4.3无向图表示及顶点覆盖判定算法 15

4.3.1 判断分子的解向量是否为覆盖 16

4.4 CRO算法求解最小顶点覆盖问题 16

4.4.1 分子编码及目标函数 16

4.4.2四种化学反应算子设计 17

4.5 结语 20

参考文献 21

致 谢 23

第1章 绪论

1.1 研究的目的及意义

在科技高速发展的今天，在调度问题和多目标优化问题上，很多的研究者已经把注意力从传统的启发式算法处，投向了化学反应优化算法。而在现代计算机高效处理复杂问题方面，化学反应优化算法已然成为了大众的焦点

这种受由粒子碰撞产生的化学反应启发的搜索算法，继承了若干其他启发式演算法诸如模拟退火算法和粒子群算法的特点。这让化学反应优化算法成为如今解决单目标优化问题的最有力的搜索算法之一。在本文中，我们提出对于多目标优化的化学反应优化算法的一种变种，通过将化学反应优化算法与NP完全问题相结合，得到了非支配排序化学反应优化算法。由于我们的方法是基于非支配排序，本文的贡献之一是探索一种基本化学反应优化算法;也因此让我们的多目标算法从编程角度来讲变的非常有效率。

化学反应优化算法的原理简单但是搜索能力却很强大，它是通过模拟化学反应中分子之间的相互作用来达到查找全局最优解的目的。经过相互作用，最后,他们被转换成为具有该层级最低能量的结构。正是凭借这个特性使得化学反应优化算法成为了搜索算法界的新宠。化学反应优化算法是学科与算法结合的完美范例，在解决连续域或离散域方面有着很好的表现。

1.2 研究背景

大多数的现实中的优化问题实际上有一个多目标性。它们通常包含几个相互矛盾的不可通约的项目，在一定的约束下进行最大或者最小化。一个多目标优化的分辨率问题（MOP）会引起一组折衷的解决方案和不同的目标之间的最佳权衡。当把它们放在目标空间，该组折衷的解决方案就是所谓的帕累托最优前沿。一些方法在专门的文献中被提出，它们近似提出对于离散情况和帕累托最优前沿持续不断的工作成果。通过模仿生物的进化原则，进化算法（EAs）在这过去几十年中通过解决MOPs积累了不小的人，而MOP的一般形式为

之所以类似的进化算法这么受欢迎都得益于：1）他们能提供一套折衷解作为单一的模拟运行解决方案的输出2）是它们对目标的几何特征功能，如非凸性，不连续性，搜索空间的不均匀性等的不敏感性。其结果是多目标进化算法(MOEAs)解决MOPs问题方面，在优化研究领域的一个新的分支的出现。这个分支被称为进化多目标优化算法（EMO），并且能称得上在研究领域计算机科学是最有吸引力和活跃的算法之。一些量身定做的分配计划在EMO文献中被提出。这些方案可作如下划分为三个类：

A．Pareto基于排名的方案

这些计划在选择规则的设计方面直接使用了Pareto 支配关系，这允许区分不同群落中的个体。首先使用Pareto支配关系并成功地生成一组非支配点是丰塞卡及菲林明。他们的算法被称为多目标遗传算法（MOGA），该算法还曾短暂的被Pareto托遗传算法（NPGA）所改进过，该算法由Horn等提出通过。无论是MOGA算法还是NPGA算法都已经在适应度赋值方面显示成效，并且这样的分配方案的效率被一些更先进的多目标进化算法的那在这些早期的设计中进一步改善。一些最值得注意他们都是非支配排序遗传算法（NSGA），NSGA-Ⅱ这是前者的改进版本，强化版Pareto EA（SPEA），它的改进版SPEA2，和Pareto信封选择算法。

B．基于指标方案