蚁群智能优化方法及其应用 - (EPUB全文下载)

文件大小：1.39 mb。
文件格式：epub 格式。
书籍内容：

蚁群智能优化方法及其应用
第1章　绪章
第2章　蚁群优化方法概述
第3章　旅行商问题
第4章　多维背包问题
第5章　定向问题
第6章　团队定向问题
第7章　属性约简
第8章　卫星资源调度问题
第9章　旅游路线规划问题
第10章　多目标组合优化问题
附录
第1章　绪章
1.1　引言
随着科学技术的进步，人类生存空间不断扩大，认识世界和改造世界的范围不断拓宽，各领域不断涌现大量的大规模、非线性、强约束的复杂优化问题。问题的计算复杂性给优化方法带来新的挑战。虽然经典优化方法的理论相对完备，然而这些方法一般只适用于具有特殊结构的优化问题。例如，单纯形算法仅适用于线性规划，不能用于非线性问题；梯度下降法假设待求解的问题是连续可微的[1]。在第二次世界大战中，美国数学家冯·诺伊曼（Von Neumann）等提出了蒙特卡罗（Monte Carlo）方法[2]，并利用刚刚诞生的电子计算机进行模拟计算，有效地解决了原子弹研制过程中出现的大量问题。人们认识到利用计算机进行“采样”可以求解优化问题。蒙特卡罗方法启发人们重新认识优化，并致力于探索新型优化方法。
自20世纪80年代以来，尤其是在最近20年，一些与经典的数学规划截然不同的、试图通过模拟自然界中的自适应优化现象求解复杂优化问题的新型智能优化算法相继出现，如遗传算法、人工免疫算法、模拟退火算法、人工神经网络、蚁群算法、粒子群优化算法等[3]，[4]，这些智能优化算法大大丰富了优化技术，也为那些传统最优化技术难以处理的优化问题提供了新的极具竞争力的解决方案。
在众多智能优化算法中，蚁群算法是最成功的算法之一[5]。该算法由意大利学者Dorigo等于20世纪90年代初提出，蚁群算法模拟蚂蚁觅食行为，将习得的信息保存在信息素场中，在产生解时，它利用问题相关的启发信息和习得的信息，而在信息加工时利用历史解信息更新信息素场，信息素场又反馈指导蚁群产生更好的解。
蚁群算法首先用于求解著名的旅行商问题（Traveling Salesman Problem，TSP），并获得了很好的计算效果[6]。此后该算法逐渐引起了国内外学者的关注，他们对该算法做了许多改进并且将其应用于更为广泛的领域，取得了一系列令人鼓舞的成果[5]。1999年，Dorigo等将其进一步发展成一种通用的优化技术——蚁群算法（Ant Colony Optimization, ACO），并将所有符合ACO框架的算法统称为蚁群算法[7]，从而为ACO的理论研究和算法设计提供了统一的框架。目前，蚁群算法的应用范围涉及城市给水排水问题[8]、卫星调度[9]、机器人领域[10][11][12][13][14]、电力系统[15][16][17][18]、故障诊断[19]、系统辨识[20]、数据挖掘[21][22][23][24][25]、图像处理[26][27][28]、航迹规划[29]，[30]、空战决策[31]、岩土工程[32]、化学工业[33]、生命科学[34]、布局优化[35]、控制参数优化[36]，[37]等科技和工程领域[38]，[39]。
1.2　复杂性理论的基础知识
一般地，优化问题可表述如下：
其中，f是目标函数，x是变量，Ω是解空间，它由一组约束定义。称解x*为全局最优的（globally optimal），如果解x*∈Ω比解空间中任意解的目标函数值小，即f（x*）≤f（x），∀x∈Ω；称解x*为子空间Θ∈Ω中局部最优的（locally optimal），如果解x*∈Θ比子解空间Θ中任意解的目标函数值小，即f（x*）≤f（x），∀x∈Θ。
在优化问题中，目标函数、约束函数和变量有不同的表现形式，对应于不同类型的优化问题。
函数类型：有许多分类标准。例如按照是否线性分为线性函数或非线性函数，相应的优化问题分别称为线性优化和非线性优化；按照是否为凸分为凸函数或非凸函数，相应的优化问题分别称为凸优化和非凸优化；按照是否连续可以分为连续函数和非连续函数，相应的优化问题分别称为连续优化和非连续优化。
函数表示：在一些问题中，函数可以给出解析表达式。但是在一些问题中，函数只能用黑盒子表示，通常只有若干采样点对应的目标函数值，例如结构设计问题。
目标函数个数：如果目标函数只有一个，则是单目标优化问题；如果不止一个，则为多目标优化问题。
函数系数类型：系数可能是确定的，也可能是动态变化的，还可能是不确定的（随机数、模糊数）。
变量类型：如果变量是函数，则是变分问题；如果变量是数值型，则又可以分为连续变量和离散变量；如果一个问题中既有连续变量也有离散变量，则该问题是混合型的。
变量个数：如果只有一个变量，则称为单变量问题，否则是多变量问题。
我们不禁要问：这些优化问题哪些是容易的，哪些是复杂的？下面依据计算复杂性理论[40]探讨这个问题。
计算复杂性理论研究至少需要多少的资源计算一类问题。所谓资源，通常是指时间和空间，即求解问题时所需的运算数和内存。相应地，复杂性分析包括时间复杂性和空间复杂性分析。
一个问题的复杂度不是指特定算法求解某个算例所需的资源，而是指求解该问题最优算法的复杂度。下面简单介绍算法复杂度和问题复杂度的基本概念。
1.2.1　算法的复杂度
评价一个算法通常从时间复杂度和空间复杂度两个方面考虑。分析算法的时间复杂度时，并不是要得到算法运行所需要的时间，而是要得到一个估计量。另一方面，运算时间只能依靠实际实验得到，因此，运算时间依赖于计算环境，用运算时间衡量复杂度意义不大。算法的运行时间与算法中语句的运算数呈正比例，如果运算数多，则运行时间就长。算法中的语句运算数称为时间频度，记为T（n），其中n是问题规模。
算法的时间复杂度是时间频度T（n）的渐近估计量。称算法的复杂度为O（T（n）），如果存在正常数n0和c使得任意n＞n0，其复杂度都小于cT（n）。也就是说，算法的复杂度与T（n）具有相同数量级，其中T（n）为n的函数。
多项式时间算法：称算法为多项式算法，如果其复杂度为O（p（n）），其中p（n）是n的多项式 ............

以上为书籍内容预览，如需阅读全文内容请下载EPUB源文件，祝您阅读愉快。