关于《迷茫的旅行商》一书-大数学家的Stewart斯图尔特院士在其封面说“…相关研究成果亦能用来实现人类苦苦追求的目标。这书堪称现世经典之作”。旅行商问题就是海南琼州大学曾经世界领先的哈密顿图问题中的最小哈密顿图问题-而也能实现人类苦苦追求目标之褒奖-正如作者Cook(美国国家工程院院士)在《迷茫的旅行商》的序说“在旅行商问题研究领域，100万美元的克雷大奖就象圣杯…。旅行商问题之所以具有永恒的力量，原因之一在于，它是应用数学以及运筹学与数学规划动态规划方向的驱动力…”，而其艰辛如Cook院士在《迷茫的旅行商》书中说“年复一年，许多无畏的数学家提出了哈密顿圈的充分条件，可是他们的猜想最后都被推翻了。…David Applegate教授在研究这问题时就将‘不屈不挠、前进到底’做为战斗口号”，也如Cook院士在第11页引用许多大师的结论：它使“整个互联网变成历史上微不足道的脚注”，“科学界、经济界、工业界将出现更加强大的工具和方法，重大突破源源不断”。正如此书第8章开头说哈佛大学读完学硕博士的图灵奖得主Karp在颁奖大会上说“我自已的所有理论成果带来的兴奋感,都比不上…”)。我们知道旅行商问题等的常规算法有:最小生成树的Kruskal算法(参看维基网)//Prim算法(维基网)//求最短路的Dijkstra算法(维基网)//Bellman-ford算法(维基网)//Floyd–Warshall
算法(维基网)//最近邻算法(维基网)//贪心算法(维基网)//插入排序算法(维基网)//模拟退火算法(维基网)//Lin-Kernighan算法,//Christofides算法(此书中说Christofides算法在旅行商问题神殿里占有重要地位,这里的著名哈密顿图定理1.9是这Christofides和法国专家得到的。关于这些算法--全世界图论第一用书邦迪的《图论及其应用》第一章的第1篇参考文献就是诺贝尔奖得主Hopcroft和Aho院士、Ullman院士合写的书《计算机算法的设计与分析》都讲到许多算法）,当然《迷茫的旅行商》也说到这些算法和下面要注解的近似算法、遗传算法、神经网络等一些重要算法。此外,关于这些算法-也可参考这里哈佛院长的《计算理论基础》和麻省院长的《计算理论导引》、评价海南琼大是国际一流的刘振宏大师翻译的普林斯顿大学大师和他的已是美国三院院士的博士合撰的《组合最优化算法和复杂性》、高度评价海南琼大工作的林诒勋大师翻译的中科院3个德国外籍院士之一的导师的《组合最优化:理论与算法》、世界第一的2企业-谷歌兼亚马逊技术总裁的《算法引论》等，除了著作还应多看一些基础性的论文如我这1991年曾和他面谈的中国运筹学常务理事秦裕瑗老师的“论算法的发现---组合优化的基本方法”等等）
其关键就如David Luenberger在他的《线性与非线性规划引论》第9页引用一名言“一个好的理论比得上一千台计算机的工作”,这也可作为上面最小哈密顿圈问题的一个最基本的思想和战略点.
第1、近似算法。在我国期刊网见我国最先5篇论文中4篇是评价海南琼州大学居于国际一流的刘振宏教授独立完成的（另1篇是北京大学张立昂教授发表在《北京化纤工学院学报》的并至今也不被引用，另有几篇非高级或非数学杂志的标题含近似算法的只具通常字面意义），在他俩之后的2篇都是马绍汉教授独立完成的且发表于《计算机学报》（如此这中国“近似算法”第一第二开拓者刘振宏教授和马绍汉教授合写的很受欢迎这里第1的《离散最优化算法》一书的最后一章就是“近似算法”，也算完成他俩做为我国最先2个开拓者的心愿，因其更比刘振宏教授翻译的《组合最优化算法和复杂性》系统许多），当然这领域也已有许多有影响的“近似算法”专著如堵丁柱院长、葛可一教授、胡旭东理事长合写的《近似算法的设计与分析》，Vijay V. Vazirani独写的《近似算法》（他的已当选美国科学院院士的胞弟也是师弟Umesh Vazirani堪称计算机理论界的第二名师并他俩的导师是图灵奖得主Manuel Blum），David P. Williamson和David B. Shmoys合撰的《近似算法的设计》等等（我国第一开拓者刘振宏大师曾评价海南琼州大学居于国际一流，并这里见他的一些简介。此外，如刘振宏和马绍汉教授合写的上面说的《离散最优化算法》也引用中国工程院首批院士许国志、刘振宏教授、邴凤山主席、谢省宗候补院士、邓述慧教授共5人主编北京大学出版社1994年出版的《现代管理科学手册》，评价海南琼州大学达到国际一流的刘振宏大师居于首批院士许国志等5个前辈权威主编们中的第二位就足见其地位（这书取材就如首批院士许国志先生写的序言说“现代管理科学的特点是管理自动化和最优化，而必采用大量运筹学的最优化技术”，这《现代管理科学手册》除了5个主编，其他撰写者都是前辈权威-如各章独立或第一撰者还有国际科学院副院长顾基发院士[写2章]、华中科技大学原副校长陈珽教授[独自写1章]、吴沧浦理事长、魏权龄教授、冯文权教授、冯士雍教授、杜金观教授、项可风教授等-可见这不仅是一本国内顶级权威书更是得以博取众多大家权威所长）。这“近似算法”领域至今已发挥极其重要作用，在我国期刊网见有2篇论文被引超过百次并它俩分别是教育部周济部长(少有的美英国工程院院士)和国防科技大学校长卢锡城院士的）
第2、遗传算法（可参考这里的教育部至今一共只通过的9本数学研究生教学用书，其中的一本就是《遗传算法的数学基础》）。遗传算法是进化计算的四种通常算法中应用最广泛的算法，此外，进化计算也已涌现出许多新模型如已很热门的量子进化算法等
第3、人工神经网络（可参考这里我对“人工神经网络”更详细的介绍）:
清华大学阎平凡和张长水教授的《人工神经网络与模拟进化计算》专著说“可以把人工神经网络理解为一个由带有突触联邦接和函数连接的结点组成的有向图”.
Hecht-Nielsen
给人工神经网络下的定义就是“人工神经网络是由人工建立的有以有向图为拓扑结构的动态系统,
它通过对连续或继续的输入作状态相应而进行信息处理”
即神经网络是一种运算模型，由大量的节点（或称神经元）之间相互联接构成。每个节点代表一种特定的输出函数，称为激励函数（activation function）。每两个节点间的连接都代表一个对于通过该连接信号的加权值，称之为权重，这相当于人工神经网络的记忆。网络的输出则依网络的连接方式，权重值和激励函数的不同而不同。而网络自身通常都是对自然界某种算法或者函数的逼近，也可能是对一种逻辑策略的表达
y =
f(∑i =1 nw
i x i -θ i)， 其中, x1 , x2 , …, x n
为节点的输入分量, 它们是神经元所接收到的信息; w1 , w2 , …, wn
为权重, 也称连接强度,
θ为阈值; f为激活函数, 一般取为非线性函数;
y为节点的输出。
人工神经网络的工作过程可分为训练和测试两个阶段。在训练阶段,
以一组输入一输出模式对作为训练样本集来训练网络。 网络训练的过程即是网络参数(包括权值、阈值等等)的调整过程。 在测试运行阶段,
给定新的输入, 网络即能计算得到相应的输出。
通常, Artificial Neural
Networks-ANN
的学习(或训练)方式可分为两种, 一种是有监督或称有导师的学习, 这时利用给定的样本标准进行分类或模仿;另一种是无监督学习或称无导师学习, 这时, 只规定学习方式或某些规则,
而具体的学习内容随系统所处的环境(即输入信号情况)而异, 系统可以自动发现环境特征和规律性,
具有更近似于人脑的功能。
刚获得诺贝尔物理学奖的彼得·希格斯指导的博士Christopher Bishop院士的专著《Neural
Networks for Pattern Recognition》也是这领域有重要参考价值的几本权威专著之一.
第4、免疫算法。国内可参考的最有影响的论文有王磊、潘进和焦李成教授的“免疫算法”以及他们其后2003年和另一王磊2002年的进一步的综述论文，特别是他们其后出版的书籍《免疫优化计算学习与识别》（中科大王煦法教授和曹先彬博士也是我国这领域的重要先驱并在期刊网见王煦法教授发表的2百多篇论文中被引最多的2篇以及被引用前20篇中一半以上都是这领域的）而且我国这些开拓性论文都是基于TSP问题-即最优哈密顿图问题这最佳试金石而发展的，最近邢立宁教授等撰写的《智能优化理论方法及其应用》和早前王凌的《智能优化算法及其应用》这2书虽不讲这免疫算法但都讲遗传算法、模拟退火算法、蚁群优化算法、粒子群优化算法等并每一算法只讲其对一类求解问题的应用即全都只讲TSP问题即最优哈密顿图问题！！！很多书都如此，这就是因TSP问题即最优哈密顿图问题是最佳试金石-最具代表性。
免疫算法一般步骤
基于抗体克隆选择学说和免疫网络学说的一般免疫算法由下面主要步骤组成.其中, 抗原、抗体、抗原和抗体之间的亲和性分别对应于优化问题的目标函数和各种约束条件、优化解、解与目标函数的匹配程度。
为了叙述算法方便, 定义F(＊)为输入抗原; P为包含有nt个网络单元(抗体) ; M∈P, 为N个记忆单元; D为抗原—抗体(Ag—Ab)间的亲合度向量; S为抗体—抗体(Ab-Ab) 间的亲合度矩阵; ζ为选择成熟分子的比率;σds 为相对自然死
亡或衰减的阀值.
步骤1 : 抗原输入 一般将目标函数和各种约束作为算法的抗原F(＊)
步骤2 : 产生初始抗体 初始抗体通常是在解空间中用随机的方法产生.与进化算法相似, 一般需要对抗体进行编码, 并且遵循完备性(completeness) 、健全性( soundness) 、和非冗余性( nonredundancy)要求.
步骤3 : 计算亲合度 分别计算抗原和抗体之间的亲合度及抗体和抗体之间的亲合度。抗体和抗体亲合度的度量一般采用解空间中的距离
sij =|pi -pj|, i =1, 2, …, nt, j =1, 2, …, nt
特别地, 如果采用二进制编码, 一般采用汉明距离表示.抗原和抗体之间的亲合度则采用抗体对抗原的适应程度(即侯选解和目标函数的匹配程度)
D ={d1, d2, …, dnt}={F( p1) , F( p2) ,…F( pnt)}
步骤4: 更新记忆单元 选择ζ%个与抗原的亲合性高的抗体加入到记忆单元M中.由于记忆单元数目有限, 祛除那些与抗原亲合度低于σds以及较大密度的记忆单元(抗体的自然死亡) .
定义Aff 为抗体记忆矩阵与抗原的平均适应度:
Aff( M) = 1/nt Σnti =1F(pi) = 1/nt Σnti =1di
因此,
Aff( M( t +1) ) ≥Aff ( M( t) )
步骤5: 产生新抗体 一般来讲, 与抗原亲合性高的抗体和低密度的抗体生存机率较大, 但是, 为了有利于优化过程的进行, 某些与抗原有较高亲合性的抗体也必须受到抑制, 从而体现了抗体克隆控制机制的多样性.可以再随机产生新的抗
体, 也可以通过变异和交叉产生进入下一代的抗体, 并将M加入新抗体群落, 祛除那些亲合度低于σds的记忆单元.提高抗体与抗原的亲合度.
P =P -α＊g( D)
步骤6: 终止条件 一般采用限定迭代次数或在连续几次(如q次) 迭代中的最好解都无法改善, 以及二者的混合形式作为终止条件.
重复执行直到满足终止条件(收敛判据)为止.
第5-1、统计学习理论(Statistical
learning theory):
现有机器学习方法共同的重要理论基础之一是统计学. 传统统计学研究的是样本数目趋于无穷大时的渐近理论. 统计学习理论 ( Statistical Learning Theory或 SLT)是一种专门研究小样本情况下机器学习规律的理论.
张学工的”关于统计学习理论与支持向量机”说”统计学习理论是建立在一套较坚实的理论基础之上的 ,为解决有限样本学习问题提供了一个统一的框架.它能将很多现有方法纳入其中 ,有望帮助解决许多原来难以解决的问题 (比如神经网络结构选择问题、局部极小点问题等 ) ;同时 ,在这一理论基础上发展了一种新的通用学习方法—— 支持向量机 ( Support Vector Machine或
SVM) ,它已初步表现出很多优于已有方法的性能.一些学者认为 , SLT和 SVM正在成为继神经网络研究之后新的研究热点 ,并将有力地推动机器学习理论和技术的发展”
机器学习的目的是根据给定的训练样本求对某系统输入输出之间依赖关系的估计 ,使它能够对未知输出作出尽可能准确的预测.可以一般地表示为: 变量 y与 x 存在一定的未知依赖关系 ,即遵循某一未知的联合概率 F(x
, y) , (x和y之间的确定性关系可以看作是其特例 ) ,机器学习问题就是根据 n个独立同分布观测样本
( x1 , y1
) , ( x2 , y2 ) ,,… , ( xn , yn) , (
1)
在一组函数 {f (x ,w)
}中求一个最优的函数 f (x , w0 )对依赖关系进行估计 ,使期望风险
R( w) = ∫ L (y , f ( x, w)
) dF(x , y) (
2)
最小。其中 , {f
(x ,w) }称作预测函数集, w为函数的广义参数 , {f ( x ,w) }可以表示任何函数集; L ( y, f ( x ,w) )为由于用 f ( x,
w)对 y进行预测而造成的损失 ,不同类型的学习问题有不同形式的损失函数 .预测函数也称作学习函数、学习模型或学习机器 .
有三类基本的机器学习问题 ,即模式识别、函数逼近和概率密度估计.对模式识别问题 ,输出 y 是类别标号,两类情况下 y= {0, 1}或 {1, - 1},预测函数称作指示函数 ,损失函数可以定义为
L ( y, f
(x, w) ) =0, if y = f (x, w)
,
1, if y ≠ f (x,
w) , (
3)
使风险最小就是 Bayes决策中使错误率最小.
在函数逼近问题中 , y是连续变量 (这里假设为单值函数 ) ,损失函数可定义为
L ( y, f
(x,w) ) = (y -f
(x, w) )2 , (
4)
即采用最小平方误差准则.
而对概率密度估计问题 ,学习的目的是根据训练样本确定 x的概率密度.记估计的密度函数为
p(x, w) ,则损失函数可以定义为
L (p(x,w)
) = - logp(x,w) . (
5)
2. 2 经验风险最小化
在上面的问题表述中 ,学习的目标在于使期望风险最小化 ,但是 ,由于我们可以利用的信息只有样本 ( 1) , ( 2)式的期望风险并无法计算 ,因此传统的学习方法中采用了所谓经验风险最小化 ( ERM)准则 ,即用样本定义经验风险
Remp (w) =∑i= 1nL ( y i , f (x i ,w) ) / n, (
6)
作为对 ( 2)式的估计 ,设计学习算法使它最小化 .对损失函数 ( 3) ,经验风险就是训练样本错误率;对 ( 4)式的损失函数 ,经验风险就是平方训练误差;而采用 ( 5)式损失函数的 ERM准则就等价于最大似然方法 .
事实上 ,用 ERM准则代替期望风险最小化并没有经过充分的理论论证 ,只是直观上合理的想当然做法 ,但这种思想却在多年的机器学习方法研究中占据了主要地位.人们多年来将大部分注意力集中到如何更好地最小化经验风险上 ,而实际上 ,即使可以假定当 n趋向于无穷大时 ( 6)式趋近于 ( 2)式 ,在很多问题中的样本数目也离无穷大相去甚远.那么在有限样本下 ERM准则得到的结果能使真实风险也较小吗?
第5-2、支持向量机(Support
Vector Machine):
支持向量机(SVM)是建立在统计学习理论基础上的一种数据挖掘方法，能非常成功地处理回归问题(时间序列分析)和模式识别(分类问题、判别分析)等诸多问题，并可推广于预测和综合评价等领域和学科。
SVM的机理是寻找一个满足分类要求的最优分类超平面，使得该超平面在保证分类精度的同时，能够使超平面两侧的空白区域最大化。理论上，支持向量机能够实现对线性可分数据的最优分类。以两类数据分类为例，给定训练样本集
( xi , yi
) , i=1,2, , l, x∈Rn , y{ ± 1},
超平面记作(w. x) +b
= 0 。(如果训练集中的所有向量均能被某超平面正确分,并且距超平面最近的异类向量之间的距离最大(即边缘最大化 ),则该超平面为最优超平面。其中距离超平面最近的异类向量被称为支持向量(Support Vector), 一组支持向量可以唯一地确定一个超平面,见崔伟东/周志华 /李星等的"支持向量机研究”)。
为使分类面对所有样本正确分类并且具备分类间隔，就要求它满足如下约束：
yi
( w. xi) +b ≥1, i=1,2,
, l,
可以计算出分类间隔为 2/ || w || ，因此构造最优超平面的问题就转化为在约束式下求：
minF (w
) =|| w ||2/2= (w¢,w
)/2
为了解决该个约束最优化问题，引入Lagrange函数：
L(w, b, a)
=|| w||/2-a( y (w. x) +b) -1)
式中， a i>0为Lagrange乘数。约束最优化问题的解由Lagrange函数的鞍点决定，并且最优化问题的解在鞍点处满足对w和b的偏导为0，将该QP问题转化为相应的对偶问题即…
第6、蚁群优化算法(Ant
colony optimization algorithms):
假设 C = {c1 , c2 , ⋯, cn } 是 n 个城市的集合, L= {l ij , c i , c j
< C} 是集合 C 中元素( 城市) 两两连接的集合, dij
( i, j = 1, 2, ⋯, n) 是 l ij 的
Euclidean 距离, G = ( C, L) 是一个有向图. TSP 问题的目的是从有向图 G 中寻出长度最短的 Hamilton 圈.
设tij ( t) 为t 时刻路径( i, j ) 上的信息素数量, m为蚂蚁群中蚂蚁的数目; G = {tij ( t) , c i , c j
< C} 是t时刻集合C 中元素两两连接l ij 上的残留信息素数量集合, 在初始时刻各条路径上信息素数量相等. 蚁群算法的寻优是在有向图G= ( C, L, G) 上通过3个准
则加以实现, 即转移概率准则、局部调整准则和全局
调整准则.
1) 转移概率准则: 蚂蚁k( k = 1, 2, ⋯, m) 在运动过程中, 根据各条路径信息素数量决定转移方向.算法中人工蚂蚁与实际蚂蚁不同, 具有记忆功能.
禁忌表 tabu k ( k = 1, 2, ⋯, m)
用来记录蚂蚁 k当前所走过的城市. 在搜索过程中, 蚂蚁根据各个路径上的信息素数量和路径的启发信息来计算转移概率. pkij
( t) 表示在t 时刻蚂蚁k 由元素i 转移到元素j的转移概率, 即
pkij ( t) =[tij ( t)]a [hij ( t)] b/(å[tis( t)]a [his ( t)] b), jÎallowed k, sÎallowed
k
0, 否则.
其中: allowed k = {C - tabu k } 表示蚂蚁 k 下一步允许选择的城市, a表示轨迹的相对重要性, b表示能见度的相对重要性[见Dorigo M , Caro
G D, Gambardella L M . Ant algo-rithms for discrete optimization . Artif icial
Life ,1999, 5(2): 137-172.] , hij ( t) 为启发函数, 即
hij ( t) = 1/ d ij
.
( 2)
显然, 该启发函数表示了蚂蚁从元素( 城市) i转移到元素( 城市) j 的期望程度.
2) 局部调整准则: 局部调整是每只蚂蚁在建立一个解的过程中进行的. 经过 h 个时刻, 两个元素状态之间的局部信息素数量要根据下式作调整:
tis ( t + h) = ( 1 - z) tis ( t) + zt0,
t0 = 1/ ( nl min ) . ( 4)
其中: zÌ[ 0, 1] , l min 表示集合C 中两个最近元素之间的距离.
3) 全局调整准则: 只有生成了全局最优解的蚂蚁才有机会进行全局调整. 全局调整规则为
tij ( t + n) = ( 1 - r) tij ( t) + rDtij ( t) ,
( 5)
Dtij ( t)=∑k= 1mDtij k ( t) . ( 6)
其中: r为挥发系数, rÌ [ 0, 1] ; Dtij ( t) 表示本次循环中路径 ij 上的信息素数量的增量; Dtij k ( t)表示第k 只蚂蚁作本次循环中留在路径 ij 上的信息量.
这些算法都来源于动物日常生活行为的启发等，并没有离常识太远的抽象，尚算好理解，就在这里仅给出个引子，各种各样的改进发展的算法也同样好理解，要做深入更多了解国外有很多名著，简略的概貌可看维基网，最新的进展有大量论文如: Dorigo
M , Maniezzo V , Colorni A . Ant system : Opti-mization by a colony of
cooperating Agents[J] . IEEE Trans on Systems , Man , and Cybernetics — Part B ,1996,
26(1): 29-41.等等
第7-1、粒子群优化算法(Particle Swarm
Optimization):
粒子群优化算法是基于群体的演化算法 , 其思想来源于人工生命和演化计算理论 。Reynolds 对鸟群飞行的研究发现, 鸟仅仅是追踪它有限数量的邻居, 但最终的整体结果是整个鸟群好像在一个中心的控制之下, 即复杂的全局行为是由简单规则的相互作用引起的 。PSO 即源于对鸟群捕食行为的研究, 一群鸟在随机搜寻食物 , 如果这个区域里只有一块食物 , 那么找到食物的最简单有效的策略就是搜寻目前离食物最近的鸟的周围区域 。PSO 算法就是从这种模型中得到启示而产生的 , 并用于解决优化问题 。另外, 人们通常是以他们自己及他人的经验来作为决策的依据, 这就构成了 PSO 的一个基本概念
PSO 求解优化问题时 , 问题的解对应于搜索空间中一只鸟的位置, 称这些鸟为“粒子”(particle)或 “主体” (agent)。每个粒子都有自己的位置和速度 (决定飞行的方向和距离), 还有一个由被优化函数决定的适应值。各个粒子记忆 、 追随当前的最优粒子 , 在解空间中搜索 。每次迭代的过程不是完全随机的, 如果找到较好解, 将会以此为依据来寻找下一个解 。
令 PSO 初始化为一群随机粒子 (随机解), 在每一次迭代中 , 粒子通过跟踪两个 “极值” 来更新自己 :第一个就是粒子本身所找到的最好解, 叫做个体极值点 (用 pbest 表示其位置), 全局版 PSO中的另一个极值点是整个种群目前找到的最好解,称为全局极值点 (用 gbest 表示其位置), 而局部版PSO 不用整个种群而是用其中一部分作为粒子的邻居, 所有邻居中的最好解就是局部极值点 (用lbest 表示其位置)。在找到这两个最好解后 , 粒子根据如下的式 (1)和式 (2)来更新自己的速度和位置。粒子 i 的信息可以用 D 维向量表示 , 位置
表示为 X i = (x i1 , x i2 , ..., x iD )T, 速度为 V i =(v i1 , v i2 , ..., v iD )T, 其他向量类似。则速度和位置更新方程为
vk+1id =vkid +c 1 rand k 1 (pbestkid -x k id )+c 2 rand k 2 (gbest k d -x k id ) (1)
x k+1id = x k id + vk+1id
vkid是粒子i 在第k 次迭代中第 d 维的速度;c 1 , c 2是加速系数 (或称学习因子), 分别调节向全局最好粒子和个体最好粒子方向飞行的最大步长 , 若太小, 则粒子可能远离目标区域 , 若太大则会导致突然向目标区域飞去, 或飞过目标区域 [ 2] 。合适的c 1 , c 2 可以加快收敛且不易陷入局部最优, 通常令 c 1 =c 2 =2; rand 1, 2 是 [ 0, 1] 之间的随机数 ; x k id是粒子 i 在第 k 次迭代中第 d 维的当前位置 ;pbest id 是粒子 i 在第d 维的个体极值点的位置 (即坐标);gbest d 是整个群在第 d 维的全局极值点的位置 。为防止粒子远离搜索空间, 粒子的每一维速度 v d 都会被钳位在 [ -v d max , +v d max ] 之间 ,v d max 太大 , 粒子将飞离最好解 , 太小将会陷入局部最优[ 2]。假设将搜索空间的第 d 维定义为区间[ -x d max , +x d max ] , 则通常 v d max =kx d max , 0.1≤k ≤1.0, 每一维都用相同的设置方法。 基本PSO 的流程可以描述为:
Step 1 初始化: 初始搜索点的位置 X0i 及其速度 V0i 通常是在允许的范围内随机产生的, 每个粒子的 pbest 坐标设置为其当前位置 , 且计算出其相应的个体极值 (即个体极值点的适应度值), 而全局极值 (即全局极值点的适应度值)就是个体极值中最好的 , 记录该最好值的粒子序号, 并将 gbest设置为该最好粒子的当前位置 。
Step 2 评价每一个粒子: 计算粒子的适应度值, 如果好于该粒子当前的个体极值, 则将 pbest设置为该粒子的位置 , 且更新个体极值 。如果所有粒子的个体极值中最好的好于当前的全局极值, 则将gbest 设置为该粒子的位置 , 记录该粒子的序号, 且更新全局极值 。
Step 3 粒子的更新:用式 (1)和式 (2)对每一个粒子的速度和位置进行更新 。
Step 4 检验是否符合结束条件: 如果当前的迭代次数达到了预先设定的最大次数 (或达到最小错误要求), 则停止迭代, 输出最优解 , 否则转到
Step 2。
第7-2、人工鱼群算法（这里最后段见它是我国学者李晓磊副教授创立的算法,这是一个最近已逐渐被国外认识和重视的一个领域-如论文2/论文1/和从数学评论可见一些外国人的论文: MR2769647/ MR2945316/ MR3132854/ MR3257682/ MR3552330/MR3537570//MR3385536， 数学家Cleve
Moler院士创办的以告数学软件为主的MathWorks公司网也用它。不过在维基网见有比它迟3年的人工蜂群算法却没它--可在期刊网见李晓磊的在国内虽更受重视啊,-我国形式上不重视的另一面是只给个副教授就几乎反映一切, 也如《社群经济：移动互联网时代未来商业驱动力》主要讲1. 鸟群/2. 蚁群/3. 蜂群算法,却没重点讲鱼群算法, 此书作者孔剑平还是“中国社群领袖峰会、全球互联网金融领袖峰会”发起人,. “社群”已是一个值得研究的课题或领域也不限于人如软件学报论文1//中国社会科学论文1//管理学报论文1//):
人工鱼群算法通过构造人工鱼来模仿鱼群的觅食、聚群及追尾行为，从而实现寻优。 为便于下文中表示,对一些符号的定义作如下说明:决策变量 X 表示人工鱼的状态AF - X ;目标函数值 Y =f(X)表示人工鱼当前状态的食物浓度 AF -foodconsistence
;d i, j =Distance(X i , X j )表示人工鱼 X i和人工鱼 X j 之间的距离;δ表示拥挤度因子 AF -delta
;trynumber 表示人工鱼每次移动时最大的试探次数;Visual 表示人工鱼的视野范围 AF - visual;Step 表示人工鱼的移动步长AF - step;AF -
Number 表示参与寻优的人工鱼的数目.因为求解极大和极小的问题可以相互转化,所以以下的介绍都以求极大问题为例进行说明.
2.4 人工鱼的行为描述
2.4.1 觅食行为
设人工鱼当前状态为 X i , 在其视野范围内随机选择一个状态 X j , 如果 Y i <Y j , 则向该方向前进一步;反之,再重新随机选择状态 X j , 判断是否满足前进条件;试探 trynumber 次后 ,如果仍不满足前进条件,则执行其他行为(如随机移动行为).
伪代码描述如下:
float
Artificial - fish::AF - prey()
{
for (i
=0;i <try - number;i ++)
{
X j =Random(N(X i ,Visual));
if (Y i >Y j )
{X i
next =X j ;
return AF - foodconsistence(X i next );}
}
X i
next =X j ;
return AF -
foodconsistence(X i next );
}
Random(N(X i ,Visual))表示在 X i 的 Visual-距离的邻域内随机取一个邻居 .
2.4.2 聚群行为
设人工鱼当前状态为 X i , 探索其邻域的伙伴数目 n f ,如果 n f / N<δ,(0<δ<1),则表明伙伴中心有较多的食物并且不太拥挤 ,如果此时 Y i <Y c , 则人工鱼向中心位置 X c 前进一步 ;否则执行其他行为(如觅食行为).
伪代码描述如下:
float
Artificial - fish::AF - swarm()
{
n f
= N(X i ,Visual) ;
X c =Center(N(X i
,Visual))
if(n f /N
<δ&&Y i <Y c )
X i next
=X c ;
else
AF - prey();
return AF -
foodconsistence(X i next );
2.4.3 追尾行为
设人工鱼当前状态为 X i , 探索其邻域内状态最优的邻居 X max ,如果 Y i <Y max , 并且 X max 的邻域内伙伴的数目 n f 满足 n f /N <δ,(0<δ<1),表明 X max 的附近有较多的食物并且不太拥挤,则向 X max 的位置前进一步;否则执行觅食行为.
伪代码描述如下:
float AF - type - A::AF - follow()
{
Y max =MAX(f(X max ),X max ∈N(X i ,Visual));
n f = N(X max ,Visual) ;
if(Y i <Y max &&n f / N<δ)
X i next =X max ;
else
AF - prey();
return AF -
foodconsistence(X i next );
}
2.4.4 约束行为
在寻优过程中, 由于聚群行为 、随机行为等操作的作用,容易使得人工鱼的状态变得不可行, 这时就需要加入相应的约束来对其进行规整化, 使它们由无效状态或不可行状态转变成可行的.
2.4.5 公告板
公告板用来记录最优人工鱼个体的状态.各人工鱼个体在寻优过程中 ,每次行动完毕就检验自身状态与公告板的状态 ,如果自身状态优于公告板状态 ,就将公告板的状态改写为自身状态,这样就使公告板记录下历史最优的状态 .
2.4.6 移动策略
根据所要解决的问题性质,对人工鱼当前所处的环境进行评价,从而选择一种合适的行为策略.可以按照进步最快的原则或者进步即可的原则来选择,如先进行追尾行为 ,如果没有进步再进行觅食行为 ,如果还没有进步则进行聚群行为,如果依然没有进步就进行随机移动行为.
综上,有了底层的人工鱼的模型, 算法的展开就在一群人工鱼的自主活动中开始了 .整个算法没有高层的指挥者,也不需要关于命题的先验知识的启发,每条人工鱼就按照自己的规则游动着,命题的满意解就这样在公告板上显示出来.算法整体表现出快速向极值域收敛的特性 ,随机移动行为的存在使得寻优活动更加全面的展开 ,从而可能到达全局极值域内.
第8、特别要说禁忌搜索算法，它是优化大师美国工程院院士Fred Glover在1986年提出的在我们组合优化学科（特别是在旅行商问题见上面《迷茫的旅行商》一书）用得最广的算法之一 …
第9、还有很多用于优化问题和人工智能等的重要算法如模拟退火算法、量子计算智能，等等
此外，根据计算机的协同计算方式组织结构以及与环境服务的关系等的若干计算模式,因不是我们关心的中心问题就仅在这里做点简介.，也因其溯源于本学科的很多领域如这里的；
最后提及与之密切的变换-就是把一堆的数据变成另一堆的数据的方法，象傅里叶变换、拉普拉斯变换、Z变换、沃尔什变换、小波变换、希尔伯特变换、离散余弦变换、哈尔变换等，这些都扩展了函数变换的定义。