蚁群算法与模拟退火算法对旅游路线问题的探究（附matlab程序） -(2)

球平均半径为R，A点北纬?i，东经?i，B点北纬?j，东经?j，基于球体几何知识因此可以得到：

OA??Rcos?i，OB??Rcos?j （1）

投影下来的 ?A?OB?=

?i??j （2）

Z ? B A O ?i?jX B’ A

Y ?i??j图2 地球经纬度 利用余弦定理可得到：

A?B?2?R2cos2?22i?Rcos?j?2?Rcos?i?Rcos?j?cos(?i??j) AB???R?(sin?i?sin?j) 利用勾股定理得到：

AB2?A?B?2?AB??2 将（3）、（4）代入（5）式中：

AB2=2R2?2R2cos?2icos?jcos(?i??j)?2Rsin?isin?j

令?AOB为?，同样利用余弦定理可得到：

AB2?R2?R2?2?R?R?cos? 化简得： co?s?cos?icos?jcos?(i??j)?sin?isin?j 则地球上两点AB之间距离即AB弧长为

AB????R?R?arcos(cos?icos?jcos(?i??j)?sin?isin?j) 即AB?为两地之间的实际路径。

6

3）

4）

5）

6）

7）

8）

9）

（ （ （ （ （（ （

因此我们根据表一中所示的各城市经纬度经过计算得到各城市间的距离（详见附录1）。

4.1.2 蚁群算法建立模型

蚁群觅食的过程与此组合优化问题的求解相似，找到一条只经过每个城市一次且回到起点的、最短路径的回路。设城市i和j之间的距离为dij。 求解中，假设蚁群算法中的每只蚂蚁是具有下列特征的简单智能体。 （1）每次周游，每只蚂蚁在其经过的支路（i，j）上都留下信息素。

（2）蚂蚁选择城市的概率与城市之间的距离和当前连接支路上所包含的信息素余量有关。

（3）为了强制蚂蚁进行合法的周游，知道一次周游完成后，才允许蚂蚁游走已访问过的城市（这可由禁忌表来控制）。

蚁群算法中的基本变量和常数有：m，蚁群中蚂蚁的总数；n，TSP问题中城市的个数；dij为城市i和j之间的距离，其中i,j?(1,34)；?ij(t)，表示t时刻在路径（i，j）连线上残留的信息量。在初始时刻各条路径上信息量相等，并设

?ij(0)=const（const为常数）。

蚂蚁k（k=1，2，?，m ）在运动过程中，根据各条路径上的信息量决定其转移方向。pijk(t)表示在t时刻蚂蚁k由城市i转移到城市j的状态转移概率，根据各条路径上残留的信息量?ij(t)及路径的启发信息?ij来计算的，如（10）所示。表示蚂蚁在选择路径时会尽量选择离自己距离较近且信息素浓度较大的方向。

???[?ij(t)]?[?ij(t)]????kpij(t)=??[?is(t)]?[?is(t)]?s?allowedk?0?j?allowed其他k （10）

allowed 式中，

k??C?tabuk?—表示在t时刻蚂蚁k下一步允许选择的城市（即

还没有访问的城市）；

tabuk（k=1，2，?，m ）—表示禁忌表，记录蚂蚁k当前已走过的城市； ?—信息启发式因子，反映了蚁群在运动过程中所残留信息量相对重要程度； ?—表示期望启发式因子，反应了期望值的相对重要程度； ?ij—表示城市i转移到城市j的期望程度，具体计算公式如下

7

?ij(t)?1dij （11）

对蚂蚁k而言，dij越小，则?ij(t)越大，pijk(t)也就越大。

为了避免残留信息素过多而淹没启发信息，在每只蚂蚁走完一步或者完成对所有n个城市的遍历后，要对残留信息素进行更新处理。（t+n）时刻在路径（i，j）上信息量可按式（3）和式（4）所示的规则进行调整。

?ij(t?n)?(1??)??ij(t)???ij(t) （12）

m ??ij(t)????k?1kij(t)

（13）

式中，?—表示信息素挥发系数。模仿人类记忆特点，旧的信息将逐步忘却、削弱。为了防止信息的无限积累，?的取值范围为[0，1），用1–?表示信息的残留系数。

??ij(t)—表示本次循环中路径（i，j）上的信息量增量，初始时刻??ij(t)?0。

??ij(t)—表示第k只蚂蚁在本次循环中留在路径（i，j）上的信息量。

k根据信息素更新策略

?Q?k??ij(t)??LK?0?Lk第k只蚂蚁在本次循环中经其他过（i,j) （14）

—表示第k只蚂蚁在本次循环中所走路径的总长度。

这里的基本蚁群算法具体算法步骤为：

第1步：初始化参数。时间t=0，循环次数Nc?0，设置最大循环次数Ncmax，令路径（i，j）的初始化信息量?ij(t)=const，初始时刻??ij(t)?0。

第2步：将m只蚂蚁随机放在n个城市上。 第3步：循环次数Nc?Nc?1。 第4步：令蚂蚁禁忌表索引号k=1。

第5步：k=k+1。

第6步：根据状态转移概率计算蚂蚁选择城市j的概率，j??C?tabuk?。 第7步：选择最大状态转移概率城市，将蚂蚁移动，把该城市计入禁忌表中。 第8步：若没有访问完集合C中的所有城市，即k?m，跳转至第5步；否则，转第9步。

8

第9步：根据式（13）和式（14）更新每条路径上的信息量。

第10步：若满足结束条件，循环结束输出计算结果；否则清空禁忌表并跳转到第3步。

9

开始 参数初始化，Nc=0 Nc?Nc?1； k=k+1 计算状态转移概率，选择下一个转移城市 修改禁忌表 Y k

图（6） 基本蚁群算法的算法框图

10

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库蚁群算法与模拟退火算法对旅游路线问题的探究（附matlab程序） -(2)在线全文阅读。