人工鱼群算法及其应用研究

VIP免费

3.0 高德中 2024-11-19 5 4 1.27MB 48 页 15积分

侵权投诉

人工鱼群算法及其应用研究

摘要

组合优化问题作为运筹学的一个重要分支，其包含的许多问题迄今为止仍是

悬而未决的 NP-难题，如旅行商问题、二次分配问题、背包问题等等，而现实生活

中的许多问题都可以被看成是组合优化问题的具体应用。对于 NP-难题的求解所需

要的计算时间随着问题规模的增大而呈指数型增长，甚至会产生失效，传统的精

确算法需要指数时间才能找到最优解，表现得不尽人意。因此，人们往往会放弃

获得问题最优解的愿望，转向探寻适合复杂计算且具有智能特征的优化算法，从

而得到问题的一个满意解决方案。随着计算机科学的发展，利用智能优化算法求

解优化问题，已经成为研究热点和重要研究方向，在优化领域更是得到了广泛的

应用。

本文的主要研究对象-人工鱼群算法。虽然该算法提出近十年，但进展缓慢。

该算法采用的是自下而上的设计方法，对寻优空间的形式和性质都没有特殊的要

求，操作简单，具有较好的全局寻优能力，并且寻优速度快。本文的具体工作包

括以下几点：

(1) 概述了计算复杂性、几类典型的组合优化问题，及求解 NP-难题常用的几

种智能优化算法及其研究现状。

(2) 利用人工鱼群算法的搜索思想，设计了能求解组合优化问题的算法，给出

了算法的数学描述、算法流程和程序实现，并探讨了该算法在求解一维和多维 0-1

背包问题中的应用，获得了满意的结果。

(3) 将人工鱼群算法扩展到求解非线性 0－1规划问题，给出了非线性 0-1 规

划的算法流程，并通过大量实验测试和与其他算法对比，从实验的角度证明了该

算法的可行性。

本文的研究成果进一步延伸了人工鱼群算法的应用范围，不仅具有很好的理

论意义，并且还有很大的应用价值。通过大量的实验证明，该算法是一种可行且

有效的智能算法，为复杂优化问题的求解提供了具有竞争力的方法，随着研究的

不断深入，其使用的范围将越来越广。

关键词：人工鱼群算法组合优化背包问题非线性 0-1规划问题

ABSTRACT

Combinatorial optimization problem is an important branch of operations research.

It includes many problems such as traveling salesman problem, quadratic assignment

problem and knapsack problem, that are still unsolved so far, and a lot of practical

problems can be treated as specific application of combinatorial optimization problems.

Solving this kind of NP-hard problem, the computing time increases with the size of the

problem and grows exponentially, even produces invalidation. Many traditional exact

algorithms need exponential time to find the optimal solution and the performances are

unsatisfactory. Therefore, people often give up the desire of gaining the optimal

solution and turn to explore optimization algorithms with intelligent characteristics for

complicated computation, and thereby get a satisfactory solution. With the development

of computer science, solving these optimization problems by intelligent optimization

algorithms, which have been widely used in the optimization, has become research

focus and important research direction.

The main object of study in this thesis is the Artificial Fish-Swarm Algorithm. This

algorithm was first proposed nearly a decade, and developed slowly. It adopts “from top

to bottom” design method, without any special requirements for the optimal space in

form and nature, operate simple, has good global optimizing ability and fast optimizing

speed. The contents of the dissertation include:

1. Generally introduces computational complexity and surveys several types of

traditional combinatorial optimization problems, some main ideas of evolutionary

algorithms which can solve NP-hard problems and their development history.

2. Using search thought of the Artificial Fish-Swarm Algorithm ,designs

algorithm to solve combinatorial optimization problems, provides its mathematics

description, algorithmic process and its programming, discusses its application in

solving one-dimensional and multi-dimensional 0-1 knapsack problem ，which give

promising results.

3. Extends applications of nonlinear 0-1 problem, based on the Artificial Fish-

Swarm Algorithm, provides its algorithm process, solves some nonlinear 0-1 problem

test of examples and compares the results with other algorithms, proves its feasibility

from the view of experiment.

The research result of the thesis develops and extends the applications of the

Artificial Fish-Swarm Algorithm. It not only possesses good theoretical significance,

but also has great application value. Many tests show that it is a kind of intelligent

algorithm with feasibility and availability, and it provides a new competitive method for

solving complex and hard optimization problems in application. With the further

research, its application range will be wider.

Key Words: Artificial Fish-Swarm algorithm, Combinatorial

optimization, knapsack problem, Nonlinear 0-1 Programming problem

目  录
中文摘要
ABSTRACT
第一章  绪论......................................................1
§1.1 研究背景...................................................1
§1.2 研究内容...................................................2
§1.3 小结.......................................................4
第二章  计算复杂性和智能优化算法..................................5
§2.1 引言.......................................................5
§2.2 计算复杂性及 NP 难题........................................5
§2.2.1 计算复杂性.............................................5
§2.2.2 NP 难题.................................................6
§2.3 智能优化算法...............................................8
§2.3.1 遗传算法...............................................9
§2.3.2 人工神经网络..........................................11
§2.3.3 模拟退火算法..........................................11
§2.3.4 禁忌搜索法............................................12
§2.3.5 蚁群优化算法..........................................13
§2.3.6 粒子群优化算法........................................14
§2.3.7 DNA算法...............................................15
§2.4 小结......................................................16
第三章  人工鱼群算法.............................................17
§3.1 群体智能..................................................17
§3.2 人工鱼群算法描述..........................................18
§3.2.1 一些定义..............................................19
§3.2.2 行为描述..............................................19
§3.2.3 行为选择..............................................21
§3.2.4 算法描述..............................................21
§3.3 算法全局收敛的基础........................................22
§3.4 各参数对收敛性能的影响分析................................23
§3.4.1 视野和步长............................................23
§3.4.2 拥挤度因子............................................24
§3.4.3 人工鱼的个体数目......................................25
§3.5 小结......................................................25
第四章  0-1背包问题的人工鱼群算法...............................26
§4.1 引言......................................................26
§4.2 0-1背包问题...............................................26
§4.2.1 一维 0-1背包问题......................................26
§4.2.2 多维 0-1背包问题......................................27
§4.3 算法描述..................................................27
§4.4 算法流程..................................................29
§4.5 算例测试..................................................29
I

§4.5.1 一维背包问题的测试算例................................29
§4.5.2 多维背包问题的测试算例................................31
§4.6 小结......................................................33
第五章  非线性 0-1规划问题的人工鱼群算法.........................34
§5.1 引言......................................................34
§5.2 非线性 0-1规划问题........................................34
§5.3 算法描述..................................................34
§5.4 算法流程..................................................36
§5.5 算例测试..................................................36
§5.6 小结......................................................41
第六章  全文总结与展望...........................................42
§6.1 全文总结..................................................42
§6.2 展望......................................................42
参考文献.........................................................44
II

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

15 积分 4人已下载

立即下载 VIP免费下载

摘要：

人工鱼群算法及其应用研究摘要组合优化问题作为运筹学的一个重要分支，其包含的许多问题迄今为止仍是悬而未决的NP-难题，如旅行商问题、二次分配问题、背包问题等等，而现实生活中的许多问题都可以被看成是组合优化问题的具体应用。对于NP-难题的求解所需要的计算时间随着问题规模的增大而呈指数型增长，甚至会产生失效，传统的精确算法需要指数时间才能找到最优解，表现得不尽人意。因此，人们往往会放弃获得问题最优解的愿望，转向探寻适合复杂计算且具有智能特征的优化算法，从而得到问题的一个满意解决方案。随着计算机科学的发展，利用智能优化算法求解优化问题，已经成为研究热点和重要研究方向，在优化领域更是得到了广泛的应用。本...

展开>> 收起<<

人工鱼群算法及其应用研究.doc

共48页,预览5页

还剩页未读，继续阅读

人工鱼群算法及其应用研究

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: