2.1 蚁群算法的基本原理
蚁群优化算法是模拟蚂蚁觅食的原理,设计出的一种群集智能算法。蚂蚁在觅食过程中能够在其经过的路径上留下一种称之为信息素的物质，并在觅食过程中能够感知这种物质的强度，并指导自己行动方向，它们总是朝着该物质强度高的方向移动,因此大量蚂蚁组成的集体觅食就表现为一种对信息素的正反馈现象。某一条路径越短,路径上经过的蚂蚁越多，其信息素遗留的也就越多,信息素的浓度也就越高,蚂蚁选择这条路径的几率也就越高,由此构成的正反馈过程,从而逐渐的逼近最优路径，找到最优路径。
蚂蚁在觅食过程时，是以信息素作为媒介而间接进行信息交流,当蚂蚁从食物源走到蚁穴,或者从蚁穴走到食物源时,都会在经过的路径上释放信息素，从而形成了一条含有信息素的路径，蚂蚁可以感觉出路径上信息素浓度的大小,并且以较高的概率选择信息素浓度较高的路径。
(a)
蚁穴 1 2 食物源
A B (b)
人工蚂蚁的搜索主要包括三种智能行为： (1）蚂蚁的记忆行为。一只蚂蚁搜索过的路径在下次搜索时就不再被该蚂蚁选择，因此在蚁群算法中建立禁忌表进行模拟。
(2）蚂蚁利用信息素进行相互通信。蚂蚁在所选择的路径上会释放一种信息素的物质,当其他蚂蚁进行路径选择时，会根据路径上的信息素浓度进行选择,这样信息素就成为蚂蚁之间进行通信的媒介。
（３)蚂蚁的集群活动。通过一只蚂蚁的运动很难达到事物源,但整个蚁群进行搜索就完全不同。当某些路径上通过的蚂蚁越来越多时，路径上留下的信息素数量也就越多，导致信息素强度增大,蚂蚁选择该路径的概率随之增加，从而进一步增加该路径的信息素强度，而通过的蚂蚁比较少的路径上的信息素会随着时间的推移而挥发,从而变得越来越少。3.3．1蚂蚁系统
蚂蚁系统是最早的蚁群算法。其搜索过程大致如下：
在初始时刻,m 只蚂蚁随机放置于城市中，各条路径上的信息素初始值相等,设为：0(0)ij ττ=为信息素初始值，可设0m m L τ=，m L 是由最近邻启发式方法构造的路径长度。其次，蚂蚁(1,2,)k k m =,按照随机比例规则选择下一步要转移
的城市，其选择概率为：
[()][()],[()][()]()0k ij ij k k is is ij s allowed t t j allowed t t p t αβ
αβτητη∈?∈??=????∑，否则
其中,ij τ为边(,)i j 上的信息素,1ij ij d η=为从城市i 转移到城市j 的启发式因子，k allowed 为蚂蚁k 下一步被允许访问的城市集合。
为了不让蚂蚁选择已经访问过的城市,采用禁忌表k tabu 来记录蚂蚁k 当前所走过的城市。经过t 时刻,所有蚂蚁都完成一次周游，计算每只蚂蚁所走过的路径长度,并保存最短的路径长度,同时,更新各边上的信息素。首先是信息素挥发,其次是蚂蚁在它们所经过的边上释放信息素,其公式如下:
(1)ij ij τρτ=- ，其中ρ为信息素挥发系数,且01ρ<≤。
1m
k ij ij ij k τττ==+?∑，其中k ij τ?是第k 只蚂蚁向它经过的边释放的信息素,定义
为:10k ij k ij
d τ???=???，如果边(i,j)在路径T 上，否则 （３．2） 根据(３.2)可知,蚂蚁构建的路径长度ij d 越小，则路径上各条边就会获得更多的信息素，则在以后的迭代中就更有可能被其他的蚂蚁选择。
蚂蚁完成一次循环后，清空禁忌表,重新回到初始城市，准备下一次周游。 大量的仿真实验发现,蚂蚁系统在解决小规模TSP 问题时性能尚可,能较快的发现最优解,但随着测试问题规模的扩大,AS 算法的性能下降的比较严重，容易出现停滞现象。因此,出现了大量的针对其缺点的改进算法。
3.３.２精英蚂蚁系统
精英蚂蚁系统［11］是对基本AS 算法的第一次改进,它首先由Dori ｇo 等人中提出,它的设计思想是对算法每次循环之后给予最优路径额外的信息素量。找出这个解的蚂蚁称为精英蚂蚁。
将这条最优路径记为bs T （bes ｔ-so-far t ｏur)。针对路径bs T 的额外强化是通过向bs T 中的每一条边增加bs L e /大小的信息素得到的,其中e 是一个参数,它定义了给予路径bs T 的权值大小，bs L 代表了bs T 的长度。这样相应的信息素的更新公式如式(３.３):
1
(1)(1)()()()m k bs ij ij ij ij k t t t e t τρτττ=+=-+?+?∑
(3.3）
其中，)(t k ij τ?的定义方法跟以前的相同,)(t bs ij τ?的定义则如式（3．4):
?????∈=? otherwise 0T j)(i, f 1)(bs ，，i L t bs bs ij
τ (3.4) Do ｒi ｇｏ等人的文章列举的计算结果表明,使用精英策略并选取一个适当的e 值将使得ＡS 算法不但可以得到更好的解，而且能够在更少的迭代次数下得到一些更好的解。
3.3.3最大-最小蚂蚁系统
最大-最小蚂蚁系统（MM AS [13-15]）是到目前为止解决ＴSP 问题最好的AC Ｏ算法方案之一。MM AS 算法是在AS 算法的基础之上，主要作了如下的改进：
（1)为避免算法过早收敛于局部最优解,将各条路径可能的外激素浓度限制于[]max min ,ττ，超出这个范围的值被强制设为m in τ或者是m ax τ，可以有效地避免某条路径上的信息量远大于其余路径,避免所有蚂蚁都集中到同一条路径上；（2）强调对最优解的利用。每次迭代结束后，只有最优解所属路径上的信息被更新，从而更好地利用了历史信息；（3）信息素的初始值被设定为其取值范围的上界。在算法的初始时刻，ρ取较小的值时,算法有更好的发现较好解的能力。所有蚂蚁完成一次迭代后，按（3．5）式对路径上的信息作全局更新:
()()()()()1,0,11∈?+?-=+ρττρτt t t best ij ij ij (3.5）
()?????=?否则
，包含在最优路径中如果边0,,1j i L best
best ij τ （3.6） 允许更新的路径可以是全局最优解,或本次迭代的最优解。实践证明逐渐增加全局最优解的使用频率，会使该算法获得较好的性能。
3.3．４基于排序的蚁群算法
基于排序的蚂蚁系统(AS rank ）[16]是对A Ｓ算法的一种改进。其改进思想是：在每次迭代完成后，蚂蚁所经路径将按从小到大的顺序排列,即)()()(21t L t L t L m ≤≤。算法根据路径长度赋予不同的权重,路径长度越短权重越大。全局最优解的权重为w ，第ｒ个最优解的权重为{}r w -,0m ax ，则AS ｒa ｎk 的信息素更新规则为:
()()()()()()()gb gb ij r r ij gb ij r ij
w r ij ij L t t L t t w t r w t t /1/11,0,)()1()1(11
=?=?∈??+??-+?-=+∑-=ττρτττρτ，其中， （3.7)
3．３.5蚁群系统
蚁群系统（ACS [1２])是由Dor ｉg ｏ等人提出来的改进的蚁群算法，它与AS 的不同之处主要体现在三个方面:(1）采用不同的路径选择规则,能更好地利用蚂蚁所积累的搜索经验。(2）信息素挥发和信息素释放动作只在至今最优路径的边上执行,即每次迭代之后只有至今最优蚂蚁被允许释放信息素；（3）除了全局信息素更新规则外,还采用了局部信息素更新规则。
在ACS 中,位于城市i 的蚂蚁k ,根据伪随机比例规则选择城市j 作为下一个访问的城市。路径选择规则由下面式子给出:
[]{}
0arg max ,k il il l allowed q q j J βτη∈?≤?=???如果，否则
（3.8)
()()()()()0k ij ij k k is is ij s allowed t t if j allowed t t p t else
αβαβτητη???????????∈?????=????????∑ (3.９)
其中,q 是均匀分布在区间[]01，中的一个随机变量，()0001q q ≤≤是一个参数，J 是根据（3.9）给出的概率分布产生出来的一个随机变量(其中1α=)。
ACS 的全局信息素更新规则为:
()1bs ij ij ij τρτρτ=-+? ， (),bs i j T ?∈
(3.10)
1bs bs ij C τ?=
(３．11)
AC Ｓ的局部信息素更新规则方式定义：
在路径构建过程中,蚂蚁每经过一条边(),i j ，都将立刻调用这条规则更新该边上的信息素:
()01ij ij τρτξτ=-+ (3.1２） 其中，ξ和0τ是两个参数，ξ满足01ξ<<,0τ是信息素量的初始值。局部更新的作用在于，蚂蚁每一次经过边(),i j ,该边的信息素ij τ将会减少,从而使得其他蚂蚁选中该边的概率相对减少。
一、一个星期七天?ＳunｄaｙＭoｎdaｙ Tｕesdaｙ Wednｅ
sday Thursdａｙ Friday Saｔurday ?二、一年十二个月
Januａｒy Feｂrｕａｒy March Ａpril Ma
ｙ Jｕnｅ
Ｊuly Aｕgust Sｅｐtｅmber Octobｅ
r Novｅmber Decembeｒ
三、一年四季?1. sｐrinｇ２. ｓummｅr ３. auｔumn ４． wiｎteｒ
四、容易拼写错的数字?1. eightｈ第八 2. nintｈ第九 3. forty四十 4. ｔｗelfｔｈ第十二５. tｗｅntiｅth第二十?四、亲属称呼
１. dａｕghｔｅr (女儿) 2． niece (女性晚辈) 3. neｐhｅw （男性晚辈)
4. coｕsin (同辈兄弟姐妹) ５. aunt (女性长辈) 6. ｕnclｅ（男性长辈)
五、以下动词加-ed或-ing要双写最后一个字母
1． regret (ｒegrｅtteｄ, ｒeｇrｅｔｔing) 后悔 2．con ｔrol （ｃontrolleｄ, conｔrｏｌｌｉｎg) 控制?３. ａdmit (adｍiｔted, admｉtｔing）承认 4． oｃcｕr (oｃcuｒred, ｏcｃｕrｒｉn ｇ) 出现?5．ｐｒｅfer (ｐrefｅrｒｅd, prefｅrrinｇ) 宁
愿 6. ｒeｆer (reｆerｒｅd, ｒefｅｒrｉnｇ) 提到
7. forget (forgeｔｔiｎg ) 忘记８. ｐeｒｍｉt (pｅrmｉｔted， permittｉｎg)允许
9. eｑｕip (ｅquiｐpeｄ, equiｐping) 装备
注意：quａrrel, sｉgnaｌ, travel中的l可双写（英国英语)也可不双写(美
国英语）?六、部分过去式和过去分词不规则变化的动词
１. broａdcast （ｂroａdcaｓt， bｒoadｃast) 广播 2．fleｅ(fled, fｌed）逃跑?３. foｒbid (ｆoｒbade, fｏrbiddｅn）禁
止 4. foｒgive (ｆorｇave，fｏrgiveｎ) 原谅
5. frｅeｚe (fｒｏze, frｏzen) 结冰
6. hanｇ (作“绞死”讲,是规则的;作“悬挂”讲,其过去式过去分词都是hun ｇ）?7．ｌie –liｅｄ–lied 说谎; lie—lay－--laｉn躺下ｌay－laid- laid 放置?８． sｅｅk (sｏｕght, sought) 寻
求 9. sｈａke (shｏoｋ, sｈaｋen) 发抖?１0． sｉng （ｓang, sｕng) 唱歌1１. ｓi
ｎk (saｎk, sｕｎk/sｕnken) 下沉?１2. sｐrｅad (ｓpread, ｓpreaｄ）
14. teaｒ (ｔo 传播 13. sｗim （swａm，ｓwum）游泳?
ｒｅ, tｏrn) 撕碎 1６．ｗear( ｗoｒe; ｗor ｎ) 穿/戴
１７．hold （ｈｅld，hｅ
ld ) 18.makｅ (made, maｄe)?1
９． kｅep (ｋept, kｅpｔ)?七、意思相近的词
１. chｅcｋ（核对)/ exａｍine(检查)/ test（测试)
2． receｉve(收到）/ aｃcepｔ(接受）?3. ｄｅsｔroy （毁坏;毁灭）/ daｍage(破坏）
4． cｅlebratｅ（庆祝)／cｏngrａtｕlaｔe（祝贺) ?5. wear sｔh
/ ｄresｓ sb 穿衣
八、注意形容词变名词时的拼写变化
1. long—lｅngth 长度２. widｅ—widtｈ宽度３. hｉgh—ｈeighｔ高度4. stroｎg—strenｇth力量?九、以-ic结尾的动词,应先把－ic变为-ick，再加ｉng或ed
１. ｐiｃnic (pｉｃｎickｅｄ, pｉｃnｉckiｎg) 野餐
十、个别名词的复数拼写?１. Germａｎ(Geｒmanｓ) 德国人 2. guｌｆ(gulfs）海湾３. handkerｃhief （handkercｈｉeｆs) 手帕roｏｆ (ｒoofs）房顶?4. hｅro (英雄),potａto (土豆），ｔomato （西红柿) 等有生命的以-o结尾的名词变复数时要加-es。?十一、注意动词变名词时的拼写变化1. suｃceeｄ—suｃcｅss成功２. proｎounce—pｒｏnｕncｉation 发音
3． expｌａiｎ—ｅｘplanaｔｉon解释 4. ｄｅcide—dｅｃisｉon 决定?5. enｔｅr—eｎtｒancｅ进入 6. pｅｒmit—permｉssion 允许
7. ｃonsiｄer—conｓideraｔｉon 考虑 8. expecｔ—expｅ
ctation 期待?９. discovｅr—diｓｃｏｖｅry 发现１０. bｕry—bｕｒiａl 埋葬?１1. ｃｏnｃlude—ｃｏnｃlusｉｏn 得出结
论1２. ａrrive—arrival 到达?１3. ｗeiｇh—wｅｉght 重
量１４. deｓcｒibe—descｒiｐtioｎ描述
15． loｓe—loss 损失16. ａｎxｉous---aｎxiｅｔｙ焦虑
十二、注意形容词变副词时的拼写变化
1. bｅaｕtiful美丽的—beautifｕlly
2. ｐｏsｓiblｅ可能的—p ｏssiｂly ?3．praｃtical实际的—pｒacticａlly 4．ｐarticｕｌaｒ特别的—pａrticｕｌarly ?5. succeｓsful成功的—ｓｕcｃessｆ
ully ?十三、其它必背单词?1. abroad 国外 2. aｂsence n. 缺席(ａbsent ａdj.) 3．aｃcepｔ接受)
4. accｉｄenｔ事故(ａccidenｔａｌ adj．偶然的，acciｄｅｎtaｌlｙａdv．偶然地) ?５. aｃhｉevｅmenｔ成就 (achieve v. 获得) ６. address地址7. ａdｍiｒe钦佩
8. admit承认(aｄmittｅd) ９. ａｇrｅｅｍｅ
10. agriculture农业(ａgｒｉculturaｌａdｊ. 农业
ｎt 协议?
的) industｒy 工业（iｎdustrial工业的）
11. altogether总共１２．aｎcient 古代的?1３. anｎounce宣告、通知 announcemenｔ ( ｎ．口头通知) 1４. anxietｙ忧虑（ａnxiｏus aｄj. 焦急的,aｎxiouｓly adv. 焦急地)
1５. apolｏgize v. 道歉 (apoｌｏgy n．道歉)
１6. apｐear 出现（aｐpｅaranｃe 外貌n．)dｉsaｐpeａｒ消失/不见?1７. ａｐprecｉａte感激/欣赏(感激人用thank sb;谢谢某人做的事用aｐpｒeciate ｓｔh.) ?1８. Asｉａn（亚洲的) 19. ａssiｓtａnｔ助手
20． astｏnｉsｈ吃惊 (aｓtonishmｅnt n. 吃惊,aｓtoｎishing令吃惊的，
21. astrｏｎaut 宇航员 22. ａtmosｐherｅａstonisheｄ吃惊的) ?
气氛
23. attempt尝试 (ｎ／ｖ) aｔtempt to ｄo sｔh
２4. attｅntiveｌｙ专心地 25. atteｎtｉｏn 专心pay ａtｔｅｎtioｎ to ｄｏｉng sｔh
26. attｉｔuｄｅ态度 2７. ａttracｔ吸引（atｔraｃｔiｏn
30. bａl 吸引力) ?２8． aｖeｒage平均 / 平均的on average 平均?
ａncｅ平衡 kｅep the balaｎce oｆ naｔure保持生态平衡?
31．ｂeauty 美 (beaｕtｉful， beauｔifully ) beautify美化?３2. bｅlｉｅve相信 (ｂｅlｉｅf n. 信念,其复数是ｂｅlieｆs）3３.
34．bｉologｙ生物35. bｉrthday生
bｅyond超过?
日
36． bｒaｖery 勇敢bｒave勇敢的ｂraｖely勇敢地
３７.bｒoad宽阔的 38. ｂroadcast广播(ｂroaｄcａsｔ; ｂroadcasｔ;) ?3９. cａre 关心ｃarefuｌ小心的careｆull
40. ceｉliｎｇ天花板41. ｃiｎｅma电影院?４2. ｙ小心地?
44． cｅn celeｂｒate庆祝４３. ceｌｅｂrａtioｎ庆祝n. ?
ｔuｒy 世纪 45. challengｅ挑战46. chaｒaｃ
47. cｈａrge收费 be cｈarge of / take chaｒge of 管ter 性格?
48. ｃｏｍforｔv. & ｎ. 安慰coｍfoｒtａble 舒适的aｄ理…?
j. ｃomfortabｌy ａdv.舒适地
50. ｃｏmｍent 评论51. ｃommuｎicate （vt）communica ｔioｎ (ｎ）交流
53. ｃ52． compｅtitioｎ竞赛(compｅte ｖ. 竞赛ｃompetitor 竞赛者) ?
oｍｐosition 作文５4. concｅｒt 音乐会
55. cｏnclude v. conclusion n．结论 56. condｉtion情况 (c ｏｎｄitｉｏns条件)
57. coｎcｅrｎ关心(ｖｔ) 58. ｃｏ
59. cｏnstａnｔ不断的ｃngratulations 祝贺 (cｏngraｔuｌate v．) ?
60. conｓtrｕctｉoｎ(建
ｏnｓtantly 不断地?
设) ６１. ｃoｎtiｎue继续
6２. contrｉｂutiｏn 贡献(contｒｉbute v.) ｍake contribuｔio ｎs to 对…做出贡献?６3. coｎvｅnienｔ (aｄj.) 方便的ｃoｎveniently方便地６4. conversatｉon 谈话
６5. cougｈing咳嗽66. cousiｎ表兄弟 67. ｃruｅl的 (ａｄj. crｕelly 残酷地ａdv.)
６８．ｃurioｕs 好奇的(ｃuｒioｓiｔy ｎ. 好奇）６9. cu ｌture(cuｌtural文化的adj.）
70. customer 顾客 72. custｏm习俗73. destrｏy毁灭（其过
去式是destｒoyed) 74．ｄｅclaｒｅ宣称 75. ｄelicｉous 美味76． dａmａｇe损坏
７7．dｅtermiｎed 有决心的 be determiｎed to ｄo sｔｈ决心做某事?７8. deｖeｌｏp发展 (devｅloｐmｅnｔn. dｅvelopiｎｇ发展中的,developed发达的）
79．dialogue 对话 8０. diary 日记 (daｉrｙ奶制品) ?8１. diffｅrｅnｃｅ不同点(复数ｄiｆｆｅrenceｓ) diffeｒent不同
的ｄifｆereｎｔly 不同地differ fｒoｍｂe diffｅreｎt fro
ｍｍake ｄifferenceｓ
８2． diｓappoiｎtｅd失望的 (ｄisappｏｉntｉng 让人失望的）８３. disaｐpoｉntmeｎｔ失望?８４. ｄiscｏvery 发现 (复数dｉsｃｏveries，
85. dｉsｔurb打扰86. 动词ｄiscｏveｒ,发现者ｄiscoverer）?
dollａr美元 (其复数是dollars) ?８7． dowｎstairs楼下upｓtair
88. dream梦想 (其过去式是dreamed或dreaｍt) ?８９.
ｓ楼上?
electricity电 (electricaｌ电的，ｅlecｔric 电的）
９0. eｍpｌoy 雇用 (eｍpｌｏymｅnt ｎ. ｅｍplｏyeｒ雇主，employ
91. ｅmpty倒空 (可用动词,其过去式是ｅmpｔieｄ）
ｅe雇员）?
92. ｅｎcｏｕrａge鼓励 (encoｕraｇｉng, enｃｏuraged, ｅncouｒagemｅｎt n.)
encｏuraｇe sb ｔo do sth 鼓励某人做某事?9３. energy能
量94. ｅnｖelope 信封 95. ｅnvy ｎ. 妒忌?9６．ｅqｕal(平等的) ｅqualｉｔy平等
９7. eｑuｉpmeｎt设备98. eｓｐeｃｉally 尤其
是99． eｓseｎtial(重要的)
100．Ｅｕroｐeａｎ欧洲人101. eｖent事件１102. eｘceｌlenｔ极好（ｅｘｃelｌence n．excelｌently 07. expert 专家?
104. exhｉbｉtion展览105. eｘpenｓｅ耗费exp aｄv.）?
10６．experience 经验/经历 (expｅrienced 有经验
ｅnｓive 昂贵的?
的）
an unusual ｅxperｉence一次不同寻常的经历hａve mｕｃｈexpｅriｅnce经验丰富
10８. exprｅss (vt) 表达exprｅ
ssion (n) 138． impress 印象 impressｉｏn （n.)
１０9． faiｌv.失败 faｉlure n.失败 fail ｔｏdo sth 没做110． fａmｉliaｒ(熟悉的) bｅｆamilｉar tｏ／wｉtｈ
成某事?
11２. fａvｏrｉtｅ最喜爱的 flexiblｅ灵活的
11 113. figure人物/数字１1４. finger手指 1１５. ｆlighｔ飞行?
11８．ｆorｔu ６. ｆorｅｈeａd前额１17. ｆoreign（外国的) ?
ｎaｔe幸运的fortunaｔelｙ幸运地ｕnfortunateｌy不幸运地?１１9．ｆoｒｗard向前120. ｆreeｚing 极冷的 (frozen 冷冻的) ?1２1． fｒeｑuentｌy 经常地122．ｆurnｉtuｒe 家具123.ｆar 远的 furｔher进一步的?１2４. generalｌy 大概 genｅrally spｅaking 一般来说
１25. ｇeographｙ地理12６. Geｒｍany德国
127. gｏveｒnmｅnt政府 128． gradｕal 逐渐的ｇrａｄｕally逐渐地
1２9． grａｄuatioｎ毕业（graduate ｆrom毕业于 ) １3０. g 131. hａbit习惯ｆorm a haｂit of 养成…习惯?1３2．ｈｒaｍmar语法?
andkercｈiｅｆ手绢) 133. honest诚实的honestｙ诚实?1３４．ｈo ｎor/hoｎoｕｒ荣誉 135. ｉmａｇinａtion 想象力（iｍagine v.）?1３6．imｍｅdiate （立即的） imｍediately马上（adv)
13９. ｉncｉdent小事件 140．including包括 (inｃｌude ｖ.)
１4１.iｎdepeｎdｅnｔ独立的142. ｉndustrｙ工业 (ｉndｕstrｉal 143. ｉｎforｍatiｏｎ信息 1４4. inｓｔruｍｅａdj. 工业的）?
nt 仪器145．ｉnstｉtｕtｅ学院
14６. iｎspｉre激励(inspirａｔｉｏn n. ｉｎsｐirinｇ鼓舞人心的, insp ｉred受鼓舞的)
147. iｎｔerest 兴趣 intｅrｅsting有兴趣的 be intｅrｅｓted in对…感兴趣
148. inｔerｒupt 打断１50．ｉntrodｕce介绍 (intｒｏｄｕctiｏn n．)
１51. regulａr规则的iｒregular 不规则的１5２. journey
旅程?１53. judge判断 (judgment) ｊudgiｎg fｒom 根据…来判断154. kｉnderｇarteｎ幼儿园１55． knowledge 知识 1５６.
labor/labour劳动?１５7. late 迟的late1y最近158. ｌa ｕgh笑laughｔer笑声
159. law法律ｌａwyｅr律师ｌｅgaｌ合法的illegaｌ非法160．lｉｂraｒｙ图书馆lｉbrarian图书馆理员
的?
１6１. lｏsｅ掉失，（ｌｏst ，ｌｏst) loss损失n.
1６２. lucｋ幸运ｌucky幸运的luｃkｉｌｙ幸运地
163. ｍａgazine杂志1６4. majｏrｉtｙ（大多数)
16６. ｍanaｇｅ设法 (maｎager经理, maｎagemenｔ管理) maｎaｇｅ
tｏdｏ设法做到．.?1６7. ｍarkeｔ(市场) ｓｕpeｒmarket超市?１68．ｍａrriａge 结婚（ｍarｒy v. 结婚，mａrriｅｄ已婚的）get marr
16９. mateｒiaｌ(s)材料) 171. maｙｏr市ｉeｄ to 与某人结婚?
172. mean (意味、打算) ｍeanｉng 意义ｍeａninｇfuｌ有意义的长?
?173. ｍeasuｒe测量take measurｅs 采取措施?１74．ｍeｄal 奖章
175. ｍemorｙ记忆力（ｍemorｉze （比较:ｍodｅｌ模型 metal 金属) ?
v．记住,ｒｅmｅmber 记得)
1７6. mｅssａge 口信１７8. mｏderｎ现代的
179．modest谦虚的180． mｏnｉtoｒ班长１8１. m ｏuｓtache 胡子
18２． muｒdｅr谋杀 (mｕｒｄerer 凶手）
184．ｍ
1８3. muｓiｃ音乐ｍusicaｌ音乐的ｍusiciａn 音乐家?ysterious 神秘的（mysｔery 神秘)
１８5．nationａｌiｔｙ国籍(ｎatiｏn 国家,natiｏｎal国家的) ?
186. nａｔure 自然naturａl自然的) １８7． naugｈty 淘气
的 188.）normaｌ正常的
190. neｃｅssarｙ必要it ｉs ｎｅcessａrｙ fｏr sb ｔｏｄｏ
ｓｔh 某人有必要做某事
1９1. obｅｙ (遵守）break 违反192. obvious 明显
的obviouslｙ明显地?１93． offｅr主动提供）oｆfer to do sｔh 194. ｏpeｒate动手术oｐｅratiｏn手术１95. oppoｒ主动做某事?
tunity 机会(=chance）
19６. ordinａrｙ普通的197. organｉｚｅ／oｒgaｎｉse(组
织) organｉzａtion组织
198．ｐarticｕlaｒｌy 特别是199． passenger 旅客200. proｂｌ
201．patieｎcｅ耐心ｐatｉeｎt耐心的;病
em难题qｕestion问题?
人(patiｅntly耐心地)
２０3. pｅｒｆect 完美(的) (pｅrfecｔly) Praｃticｅ maｋes pｅｒｆeｃt．熟能生巧
2０4. perfoｒm (表演) 20５. perhaｐs 或许２0６. pｅrｉｏd 时期
20８. pｅrsuａded(说207. peｒmｉt 许可 vt permｉｓsiｏｎ许可 n ?
服) 2０９. ｐｈeｎｏｍeｎｏn 现象ｐhenoｍena 现象（复数）
21０. pｈysicist 物理学家211. piｌot (飞行员)
212. ｐｏｉsonｏus 有毒的 (poison) 213．poｌitｉcａl 政治的 (ｐoliticｓ)
21４. ｐｏｐular受欢迎的215. poｐｕlaｔion人口21６. posｉtｉon 职位?2１７. poｓsibilｉty(－ies）可能性（posｓible 可能的) ２18. p ｏverｔy 贫穷n (pooｒ贫穷的） 2２０. pｒaｃticｅ实践practicaｌ(可实施的，实际的)
2２１．ｐrepaｒe（准备) prepａｒａｔiｏn 222. press 压／按ｐ
223．ｐretend假装pretend tｏ dｏ sth 假装做rｅｓｓｕre（压力) ?
某事
224. profｅssｏr 教授225．ｐroｆit 利润?
226. progress进步
22７. ｐronｏｕnce发音proｎuncｉａｔｍake good prｏgress进步很大?
ioｎ（n.发音）
228. ｐrovide 提供（比较: sｕpply/ pｒovｉde sb wｉth ｓtｈoｆfer ｓb sth提供某人某物，
229. publｉc 公众２30. ｐuｒpose目的ｏn purpoｓｅ故意地
233. realize (实现ｖ2３1． quaｌity质量/素质232． quantity（数量?
t) realiｔy ｎ.现实2３4. receivｅ收到?2３5. recentｌy(最近236. recycｌe( 循环再用）２３7. ｒecognize 认出
= latelｙ) ?
?238. ｒegardｓ问候 give ｍy regards tｏｓb请带我向某人问候
2３9. remｉnd提醒 reｍind sb of sth 提醒某人某物?２40. ｒepｅ
at vｔ.重复(reｐｅtition n.重复) 241. respeｃt尊敬?242．resｔａｕranｔ餐馆
24 2４4. satｉsfａｃtioｎ满意(saｔisfy, ｓatisfｉed, satisfyiｎg）?６. Saturdａy(星期六) ２47. scientific 科学的
2４８. sciｅntific科学的249. sｅcretarｙ秘书
25０. secrｅtlｙ (秘密地) ２51. seｐarateｌy单独地2５２. sｅpar
蚁群算法简述及实现 1 蚁群算法的原理分析 蚁群算法是受自然界中真实蚁群算法的集体觅食行为的启发而发展起来的一种基于群体的模拟进化算法,属于随机搜索算法,所以它更恰当的名字应该叫“人工蚁群算法”,我们一般简称为蚁群算法。M.Dorigo等人充分的利用了蚁群搜索食物的过程与著名的TSP问题的相似性,通过人工模拟蚁群搜索食物的行为来求解TSP问题。 蚂蚁这种社会性动物,虽然个体行为及其简单,但是由这些简单个体所组成的群体却表现出及其复杂的行为特征。这是因为蚂蚁在寻找食物时,能在其经过的路径上释放一种叫做信息素的物质,使得一定范围内的其他蚂蚁能够感觉到这种物质,且倾向于朝着该物质强度高的方向移动。蚁群的集体行为表现为一种正反馈现象,蚁群这种选择路径的行为过程称之为自催化行为。由于其原理是一种正反馈机制,因此也可以把蚁群的行为理解成所谓的增强型学习系统(Reinforcement Learning System)。 引用M.Dorigo所举的例子来说明蚁群发现最短路径的原理和机制,见图1所示。假设D 和H之间、B和H之间以及B和D之间(通过C)的距离为1,C位于D和B的中央(见图1(a))。现在我们考虑在等间隔等离散世界时间点(t=0,1,2……)的蚁群系统情况。假设每单位时间有30只蚂蚁从A到B,另三十只蚂蚁从E到D,其行走速度都为1(一个单位时间所走距离为1),在行走时,一只蚂蚁可在时刻t留下浓度为1的信息素。为简单起见,设信息素在时间区间(t+1，t+2)的中点(t+1.5)时刻瞬时完全挥发。在t=0时刻无任何信息素,但分别有30只蚂蚁在B、30只蚂蚁在D等待出发。它们选择走哪一条路径是完全随机的,因此在两个节点上蚁群可各自一分为二,走两个方向。但在t=1时刻,从A到B的30只蚂蚁在通向H的路径上(见图1(b))发现一条浓度为15的信息素,这是由15只从B走向H的先行蚂蚁留下来的;而在通向C的路径上它们可以发现一条浓度为30的信息素路径,这是由15只走向BC的路径的蚂蚁所留下的气息与15只从D经C到达B留下的气息之和(图1(c))。这时,选择路径的概率就有了偏差,向C走的蚂蚁数将是向H走的蚂蚁数的2倍。对于从E到D来的蚂蚁也是如此。 （a）（b）（c） 图1 蚁群路径搜索实例 这个过程一直会持续到所有的蚂蚁最终都选择了最短的路径为止。 这样,我们就可以理解蚁群算法的基本思想:如果在给定点,一只蚂蚁要在不同的路径中选择,那么,那些被先行蚂蚁大量选择的路径(也就是信息素留存较浓的路径)被选中的概率就更大,较多的信息素意味着较短的路径,也就意味着较好的问题回答。
大连理工大学 研究生必修课 作业 课程名称：现代物流管理 研究生姓名：徐静学号：21511149 作业成绩： 任课教师(签名) 交作业日时间：2016 年6 月1日
蚁群算法在TSP问题上的应用 摘要蚁群算法是受现实蚂蚁群体行为启发而得出的一类仿生算法。本文以解决TSP问题为基础,系统地介绍了蚁群算法从诞生到成熟过程中几个代表性的算法。在阐述算法基本思想的前提下，着重论述算法的创新之处。 关键词蚁群算法，TSP问题，蚁群优化 1引言 蚁群算法也称作蚁群优化(Ant Colony Optimization，ACO)，最早是由Dorigo及其研究同伴所提出，用于求解诸如旅行商问题之类的组合优化问题。自然界蚂蚁在其经过的路径上会留下某种生物信息物质(信息素)，该物质会吸引蚁群中的其它成员再次选择该段路径；食物与巢穴之前较短的路径容易积累较多的信息素，因而使得更多的蚂蚁选择走该段路径，最终几乎所有的蚂蚁都集中在最短路径上完成食物的搬运。Dorigo等从此现象中抽象出路径选择和信息素积累的数学模型，作为蚁群算法的核心，并通过对蚂蚁寻找最短路径的计算机模拟，实现了对TSP问题的求解。自此，蚁群算法越来越多地被用于求解其它的组合优化问题，也被推广到工业工程上应用。 蚁群算法特点是并发性、鲁棒性、正反馈性等。在蚁群算法求解问题的过程中，利用蚁群在问题空间中同时构造问题的多个解体现了算法的并发性。蚁群不会因为单个蚂蚁寻找到较差的解或者因为问题空间发生改变而使得算法丧失作用，这体现了算法的鲁棒性。在蚂蚁构造问题解的过程中，以蚁群觅食行为为例，会在经过的解路径上释放信息素，而解空间中获得信息素越多的路径，对蚂蚁的吸引力就越大，使更多的蚂蚁经过该路径并进一步在上面释放信息素，这体现了算法的正反馈性。 TSP问题代表一类组合优化问题，在实际工程中有许多应用，如计算机联网、电子地图、交通诱导、电气布线、VLSI单元布局、ATM分组交换网等。鉴于其重要的工程与理论价值，TSP常作为算法性能研究的典型算例。求其最优解的代价是指数级的，因此对其近似解的研究一直是算法设计的一个重要课题。 TSP问题是典型的NP完全问题，许多算验证法及算法效率测试都以TSP问题为基础。在蚁群算法研究中，第一个蚁群算法，蚂蚁系统,就是在TSP问题的基础上提出来的。而后，依据TSP问题，又提出了蚁群算法系列中具有代表性的蚁群系统、最大——最小蚂蚁系统。 本文以TSP问题为基础,对蚁群算法的基本问题及典型的蚁群算法进行了综述。涉及到算法的基本问题、算法描述、算法改进及意义。通过研究总结了蚁群算法的发展历程和实现思想。
动态规划算法原理及其应用研究 系别：x x x 姓名：x x x 指导教员： x x x 2012年5月20日
摘要：动态规划是解决最优化问题的基本方法，本文介绍了动态规划的基本思想和基本步骤，并通过几个实例的分析，研究了利用动态规划设计算法的具体途径。关键词：动态规划多阶段决策 1.引言 规划问题的最终目的就是确定各决策变量的取值，以使目标函数达到极大或极小。在线性规划和非线性规划中，决策变量都是以集合的形式被一次性处理的；然而，有时我们也会面对决策变量需分期、分批处理的多阶段决策问题。所谓多阶段决策问题是指这样一类活动过程：它可以分解为若干个互相联系的阶段，在每一阶段分别对应着一组可供选取的决策集合；即构成过程的每个阶段都需要进行一次决策的决策问题。将各个阶段的决策综合起来构成一个决策序列，称为一个策略。显然，由于各个阶段选取的决策不同，对应整个过程可以有一系列不同的策略。当过程采取某个具体策略时，相应可以得到一个确定的效果，采取不同的策略，就会得到不同的效果。多阶段的决策问题，就是要在所有可能采取的策略中选取一个最优的策略，以便得到最佳的效果。动态规划是一种求解多阶段决策问题的系统技术，可以说它横跨整个规划领域（线性规划和非线性规划）。在多阶段决策问题中，有些问题对阶段的划分具有明显的时序性，动态规划的“动态”二字也由此而得名。动态规划的主要创始人是美国数学家贝尔曼（Bellman）。20世纪40年代末50年代初，当时在兰德公司（Rand Corporation）从事研究工作的贝尔曼首先提出了动态规划的概念。1957年贝尔曼发表了数篇研究论文，并出版了他的第一部著作《动态规划》。该著作成为了当时唯一的进一步研究和应用动态规划的理论源泉。在贝尔曼及其助手们致力于发展和推广这一技术的同时，其他一些学者也对动态规划的发展做出了重大的贡献，其中最值得一提的是爱尔思（Aris）和梅特顿（Mitten）。爱尔思先后于1961年和1964年出版了两部关于动态规划的著作，并于1964年同尼母霍思尔（Nemhauser）、威尔德（Wild）一道创建了处理分枝、循环性多阶段决策系统的一般性理论。梅特顿提出了许多对动态规划后来发展有着重要意义的基础性观点，并且对明晰动态规划路径的数
第一章绪论 1.每18个月芯片的性能和速度均提高一倍，每隔12年软件生产大约提高一倍。 2.软件：是能够完成预定功能和性能的可执行的计算机诚信度。包括使程序正常执行所需的数据，以及有关描述程 序操作和使用的文档。即：软件= 程序+ 文档 3.软件的特征： 软件的开发不同于硬件设计、不同于硬件制造、不同于硬件维修。 4.软件危机出现的原因： 软件维护费用的急剧上升，直接威胁计算机应用的扩大； 软件生产技术进步缓慢，是家居软件危机的重要原因。 -------------------------------------------------------------------------------------------------------------------------------------------------------------------- 5.软件工程学的范畴： 软件开发技术（软件开发方法学、软件工具、软件工程环境）、软件工程管理（软件管理学、软件经济学、度量学）。 6.软件工程：是指导计算机软件开发和维护的工程学科。它采用工程的概念、原理、技术和方法来开发与维护软件， 目的是为了实现按照预期的进度和经费完成软件生产计划，同时提高软件的生产率和可靠性。 7.软件的发展：大体经历了程序、软件、软件产品3个阶段。 8.工具和方法是软件开发技术的2大支柱。 9.3种编程泛型： 过程式编程泛型、面向对象编程泛型、基于构件技术的编程泛型 10.面向对象程序设计中，数据和操作被封装在一个对象中，对象之间则是通过消息相互联系。 11.构件：标准化/规格化的对象类。 12.常用变成力度的大小来比较3种编程泛型的差异。 粒度由小到大依次是：过程式编程范式、面向对象编程范式、基于构件的编程泛型。 13.软件工程的分化： 传统软件工程：结构化分析-》结构化设计-》面向过程编码-》软件测试 面向对象软件工程：OO分析与对象抽取-》对象详细设计-》面向对象的编码与测试 基于构件的软件工程（以可复用构件和测试工具为后盾）： 领域分析和测试计划定制-》领域设计-》建立可复用构件库-》按‘构件集成模型’查找与集成构件 14.分析先于设计，设计先于编码，使程序（的结构）适合于问题（的结构）。 第二章软件生存周期与软件过程 1.软件生存周期：计划、开发、运行3个时期。 需求分析-》软件分析-》软件设计-》编码测试-》软件测试-》运行维护 2.需求分析（用户视角）：功能需求、性能需求、环境约束、外部接口描述。 3.软件分析（开发人员视角）：建立与需求模型一致的，与实现无关的软件分析模型。 4.软件设计：总体设计/概要设计、详细设计（确定软件的数据结构和操作）。 5.单元测试通常与编码同时进行。 6.软件测试：单元测试、集成测试、系统测试。 7.Boehm软件生存周期的划分：系统需求、软件需求、概要设计、详细设计、编码纠错、测试和预运行、系统维护。-------------------------------------------------------------------------------------------------------------------------------------------------------------------- 8.瀑布模型特点：阶段间的顺序性和依赖性、推迟实现的观点、保证质量的观点。 9.瀑布模型存在的问题：只有在需求分析准确的前提下，才能得到预期的结果。 快速原型模型：原型系统只包括对未来系统的主要功能以及系统的重要接口。特点：快速开发工具、循环、低成本。种类：渐进型、抛弃型。
蚁群算法浅析 摘要：介绍了什么是蚁群算法，蚁群算法的种类，对四种不同的蚁群算法进行了分析对比。详细阐述了蚁群算法的基本原理，将其应用于旅行商问题，有效地解决了问题。通过对旅行商问题C++模拟仿真程序的详细分析，更加深刻地理解与掌握了蚁群算法。 关键词：蚁群算法；旅行商问题；信息素；轮盘选择 一、引言 蚁群算法（Ant Colony Optimization, ACO），是一种用来在图中寻找优化路径的算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法，初步的研究表明该算法具有许多优良的性质。 蚁群算法成功解决了旅行商问题（Traveling Salesman Problem, TSP）：一个商人要到若干城市推销物品，从一个城市出发要到达其他各城市一次而且最多一次最后又回到第一个城市。寻找一条最短路径，使他从起点的城市到达所有城市一遍，最后回到起点的总路程最短。若把每个城市看成是图上的节点，那么旅行商问题就是在N个节点的完全图上寻找一条花费最少的回路。 最基本的蚁群算法见第二节。目前典型的蚁群算法有随机蚁群算法、排序蚁群算法和最大最小蚁群算法，其中后两种蚁群算法是对前一种的优化。本文将终点介绍随机蚁群算法。 二、基本蚁群算法 （一）算法思想 各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。当一只找到食物以后，它会向环境释放一种信息素，信息素多的地方显然经过这里的蚂蚁会多，因而会有更多的蚂蚁聚集过来。假设有两条路从窝通向食物，开始的时候，走这两条路的蚂蚁数量同样多（或者较长的路上蚂蚁多，这也无关紧要）。当蚂蚁沿着一条路到达终点以后会马上返回来，这样，短的路蚂蚁来回一次的时间就短，这也意味着重复的频率就快，因而在单位时间里走过的蚂蚁数目就多，洒下的信息素自然也会多，自然会有更多的蚂蚁被吸引过来，从而洒下更多的信息素。因此，越来越多地蚂蚁聚集到较短的路径上来，最短的路径就找到了。 蚁群算法的基本思想如下图表示：
（计算智能大作业） 应用蚁群算法求解TSP问题
目录 蚁群算法求解TSP问题 (3) 摘要： (3) 关键词： (3) 一、引言 (3) 二、蚁群算法原理 (4) 三、蚁群算法解决ＴＳＰ问题 (7) 四、解决ｎ个城市的TSP问题的算法步骤 (9) 五、程序实现 (11) 六、蚁群算法优缺点分析及展望 (18) 七、总结 (18)
采用蚁群算法解决TSP问题 摘要：蚁群算法是通过蚂蚁觅食而发展出的一种新的启发算法，该算法已经成功的解决了诸如TSP问题。本文简要学习探讨了蚂蚁算法和TSP问题的基本内容，尝试通过matlab 仿真解决一个实例问题。 关键词：蚁群算法；TSP问题；matlab。 一、引言 TSP（Travelling Salesman Problem）又称货郎担或巡回售货员问题。TSP问题可以描述为：有N个城市，一售货员从起始城市出发，访问所有的城市一次，最后回到起始城市，求最短路径。TSP问题除了具有明显的实际意义外，有许多问题都可以归结为TSP问题。目前针对这一问题已有许多解法，如穷举搜索法（Exhaustive Search Method）, 贪心法（Greedy Method）, 动态规划法（Dynamic Programming Method）分支界定法（Branch-And-Bound），遗传算法（Genetic Agorithm）模拟退火法(simulated annealing),禁忌搜索。本文介绍了一种求解TSP问题的算法—蚁群算法，并通过matlab仿真求解50个城市之间的最短距离，经过仿真试验，证明是一种解决TSP问题有效的方法。
下面的程序是蚁群算法在最短路中的应用，稍加扩展即可应用于机器人路径规划 function [ROUTES,PL,Tau]=ACASP(G,Tau,K,M,S,E,Alpha,Beta,Rho,Q) %% --------------------------------------------------------------- % ACASP.m % 蚁群算法动态寻路算法 % ChengAihua,PLA Information Engineering University,ZhengZhou,China % Email:aihuacheng@https://www.doczj.com/doc/917779916.html, % All rights reserved %% --------------------------------------------------------------- % 输入参数列表 % G 地形图为01矩阵，如果为1表示障碍物 % Tau 初始信息素矩阵（认为前面的觅食活动中有残留的信息素） % K 迭代次数（指蚂蚁出动多少波） % M 蚂蚁个数（每一波蚂蚁有多少个） % S 起始点（最短路径的起始点） % E 终止点（最短路径的目的点） % Alpha 表征信息素重要程度的参数 % Beta 表征启发式因子重要程度的参数 % Rho 信息素蒸发系数 % Q 信息素增加强度系数 % % 输出参数列表 % ROUTES 每一代的每一只蚂蚁的爬行路线 % PL 每一代的每一只蚂蚁的爬行路线长度 % Tau 输出动态修正过的信息素 %% --------------------变量初始化---------------------------------- %load D=G2D(G); N=size(D,1);%N表示问题的规模（象素个数） MM=size(G,1); a=1;%小方格象素的边长 Ex=a*(mod(E,MM)-0.5);%终止点横坐标 if Ex==-0.5 Ex=MM-0.5; end Ey=a*(MM+0.5-ceil(E/MM));%终止点纵坐标 Eta=zeros(1,N);%启发式信息，取为至目标点的直线距离的倒数 %下面构造启发式信息矩阵 for i=1:N if ix==-0.5 ix=MM-0.5; end
蚁群算法原理及在TSP 中的应用 1 蚁群算法（ACA ）原理 1.1 基本蚁群算法的数学模型 以求解平面上一个n 阶旅行商问题(Traveling Salesman Problem ，TSP)为例来说明蚁群算法ACA （Ant Colony Algorithm ）的基本原理。对于其他问题，可以对此模型稍作修改便可应用。TSP 问题就是给定一组城市，求一条遍历所有城市的最短回路问题。 设()i b t 表示t 时刻位于元素i 的蚂蚁数目，()ij t τ为t 时刻路径(,)i j 上的信息量，n 表示TSP 规模，m 为蚁群的总数目，则1()n i i m b t ==∑；{(),}ij i i t c c C τΓ=?是t 时刻集合C 中元素(城市)两两连接ij t 上残留信息量的集合。在初始时刻各条路径上信息量相等，并设 (0)ij const τ=，基本蚁群算法的寻优是通过有向图 (,,)g C L =Γ实现的。 蚂蚁(1,2,...,)k k m =在运动过程中，根据各条路径上的信息量决定其转移方向。这里用禁忌表(1,2,...,)k tabu k m =来记录蚂蚁k 当前所走过的城市，集合随着 k tabu 进化过程作动态调整。在搜索过程中，蚂蚁根据各条路径上的信息量及路 径的启发信息来计算状态转移概率。()k ij p t 表示在t 时刻蚂蚁k 由元素(城市)i 转移 到元素(城市)j 的状态转移概率。 ()*()()*()()0k ij ij k k ij ij ij s allowed t t j allowed t t p t αβ αβτητη??????????? ∈?????=????? ??? ∑若否则 (1) 式中，{}k k allowed C tabuk =-表示蚂蚁k 下一步允许选择的城市；α为信息启发式因子，表示轨迹的相对重要性，反映了蚂蚁在运动过程中所积累的信息在蚂蚁运动时所起作用，其值越大，则该蚂蚁越倾向于选择其他蚂蚁经过的路径，蚂蚁之间协作性越强；β为期望启发式因子，表示能见度的相对重要性，反映了蚂蚁在运动过程中启发信息在蚂蚁选择路径中的重视程度，其值越大，则该状态转移概率越接近于贪心规则；()ij t η为启发函数，其表达式如下： 1 ()ij ij t d η= (2)
https://www.doczj.com/doc/917779916.html,/sun_raining61/blog/item/449da9240b1e71024d088d5d.html/cmtid/1056b bed39d4d24779f05502 using System; using System.Collections.Generic; using System.Text; namespace AntSystem { public class AA { /**////
《智能计算—蚁群算法基本综述》 班级：研1102班 专业：计算数学 姓名：刘鑫 学号： 1107010036 2012年
蚁群算法基本综述 刘鑫 （西安理工大学理学院，研1102班，西安市，710054） 摘要:蚁群算法( ACA)是一种广泛应用于优化领域的仿生进化算法。ACA发展背景着手，分析比较国内外ACA研究团队与发展情况立足于基本原理,分析其数学模型,介绍了六种经典的改进模型，对其优缺点进行分析，简要总结其应用领域并对其今后的发展、应用做出展望。 关键词:蚁群；算法；优化；改进；应用 0引言 专家发现单个蚂蚁只具有一些简单的行为能力。但整个蚁群却能完成一系列复杂的任务。这种现象是通过高度组织协调完成的1991年。意大利学者M.Dorigo 首次提出一种新型仿生算法ACA。研究了蚂蚁的行为。提出其基本原理及数学模型。并将之应用于寻求旅行商问题(TSP)的解。 通过实验及相关理论证明,ACA有着有着优化的选择机制的本质。而这种适应和协作机制使之具有良好的发现能力及其它算法所没有的优点。如较强的鲁棒性、分布式计算、易与其他方法结合等；但同时也不应忽略其不足。如搜索时间较长，若每步进行信息素更新，计算仿真时所占用CPU时间过长：若当前最优路径不是全局最优路径，但其信息素浓度过高时。靠公式对信息素浓度的调整不能缓解这种现象。会陷人局部收敛无法寻找到全局最优解：转移概率过大时，虽有较快的收敛速度，但会导致早熟收敛。所以正反馈原理所引起的自催化现象意在强化性能好的解，却容易出现停滞现象。笔者综述性地介绍了ACA对一些已有的提出自己的想法，并对其应用及发展前景提出了展望。 1 蚁群算法概述 ACA源自于蚁群的觅食行为。S.Goss的“双桥”实验说明蚂蚁总会选择距食物源较短的分支蚂蚁之间通过信息素进行信息的传递,捷径上的信息素越多,吸引的蚂蚁越多。形成正反馈机制,达到一种协调化的高组织状态该行为称集体自催化目前研究的多为大规模征兵，即仅靠化学追踪的征兵。 1 .1 蚁群算法的基本原理
软——应 课习题 件工程原理、方法与用后答案最完整版 绪论 1.什么是软件危机？为什么会产生软件危机？ 答：软件危机是指在计算机软件的开发和维护过程中遇到的一系列严重问题。 (1).软件维护费用急剧上升，直接威胁计算机应用的夸大。 (2).软件生产技术进步缓慢 2. 什么是软件生产工程化？工程化生产方法与早期的程序设计方法主要差别在哪里？ 答：结构化程序设计地出现，使许多产业界认识认识到必须把软件生产从个人化方式改变为工程化。采用工程的概念、原理、技术和方法开发与维护软件，把经过时间考验而证明正确的管理技术和当前能够得到的最好的技术方法结合起来，以经济地开发出高质量的软件并有效地维护它，这就是软件工程，同时这也是工程化生产方法。 3. 分别说明（1）软件开发方法与开发工具；（2）软件技术与软件管理的相互关系。 答：（1）工具和方法，是软件开发技术的两大支柱，它们密切相关。当一种方法提出来并证明有效后，往往随之研制出相应的工具，来帮助实现和推行这种方法。新方法在推行初期，总有人不愿接受和采用。若将新方法融合于工具之中，使人们通过使用工具来了解新方法，就能更快促进新方法的推广。 （2）在工业生产中，即使有先进的技术和设备，管理不善的企业也不能获得良好的效益。 软件在生产中不能按质按时完成计划，管理混乱往往是其中的重要原因。所以对于一个理想的软件工程环境，应该同时具备技术和管理两个方面。 4.试从你的亲身实践，谈谈软件工具在软件开发中的作用。 答：用C++开发一个软件，是校园一卡通的模块。首先，要在编辑程序支持下在计算机中输入源程序。然后编译程序，把源程序翻译成目标程序。如果发现错误，就重新调入编辑程序对源程序进行修改。编译通过后，再调用连接程序吧所有通过了编译目标程序连同与之有关的程序连接起来，构成一个能在计算机上运行的可执行软件。编译程序，编辑程序，连接程序以及支持他们的计算机操作系统，都属于软件工具。离开这些工具，软件开发就是去了支持，变得十分困难和低效，甚至不能运行。5.什么是软件工程环境？谈谈你对环境重要性的认识。 答：方法与工具相结合，再加上配套的软、硬件支持就形成环境。例如在批处理时代，用户开发的程序是分批送入计算机中心的计算机的，有了错误，就得下机修改。程序员对自己写的程序只能继续地跟踪，思路经常被迫中断，效率难于提高。分时系统的使用，使开发人员从此能在自己的终端上跟踪程序的开发，仅此一点，就明显提高了开发的效率。 6. 何谓面向对象软件工程？简述它与传统软件工程在各型软件开发中的作用。 答：以面向对象程序设计为基础。 7. 软件按规模大小可分成哪几类？简述软件工程中各型软件开发中的作用。 答：按规模分为极小、小、中、大、甚大、极大。 （1）中小型软件：软件工程对改进软件质量，提高程序员生产率和满足用户的需求，有很大的作用。（2）大型软件：这类软件必须从头至尾坚持软件工程的方法，严格遵守标准文档格式和正规的复审制度，才能避免或减少混乱，真正开发出大型的软件。 8. 什么是形式化软件开发方法？实现这类开发的困难和出路在哪里？
分子对接的原理，方法及应用 （PPT里弄一些分子对接的照片，照片素材文件里有） 分子对接 是将已知三维结构数据库中的分子逐一放在靶标分子的活性位点处。通过不断优化受体化合物的位置、构象、分子内部可旋转键的二面角和受体的氨基酸残基侧链和骨架，寻找受体小分子化合物与靶标大分子作用的最佳构象，并预测其结合模式、亲和力和通过打分函数挑选出接近天然构象的与受体亲和力最佳的配体的一种理论模拟分子间作用的方法。 通过研究配体小分子和受体生物大分子的相互作用，预测其亲和力，实现基于结构的药物设计的一种重要方法。 原理： 按照受体与配体的形状互补，性质互补原则，对于相关的受体按其三维结构在小分子数据库直接搜索可能的配体，并将它放置在受体的活性位点处，寻找其合理的放置取向和构象，使得配体与受体形状互补，性质互补为最佳匹配 （配体与受体结合时，彼此存在静电相互作用，氢键相互作用，范德华相互作用和疏水相互作用，配体与受体结合必须满足互相匹配原则，即配体与受体几何形状互补匹配，静电相互作用互补匹配，氢键相互作用互补匹配，疏水相互作用互补匹配） 目的： 找到底物分子和受体分子的最佳结合位置 问题： 如何找到最佳的结合位置以及如何评价对接分子之间的结合强度 方法： 1、首先建立大量化合物的三维结构数据库 2、将库中的分子逐一与靶分子进行“对接” 3、通过不断优化小分子化合物的位置以及分子内部柔性键的二面角，寻找小分子化合物与靶标大分子作用的最佳构象，计算其相互作用及结合能 4、在库中所有分子均完成了对接计算之后，即可从中找出与靶标分子结合的最佳分子 应用： 1）直接揭示药物分子和靶点之间的相互作用方式 2）预测小分子与靶点蛋白结合时的构象 3）基于分子对接方法对化合物数据库进行虚拟筛选，用于先导化合物的发现
蚁群算法的改进与应用 摘要：蚁群算法是一种仿生优化算法，其本质是一个复杂的智能系统，它具有较强的鲁棒性、优良的分布式计算机制和易于与其他方法结合等优点。但是现在蚁群算法还是存在着缺点和不足,需要我们进一歩改进,如：搜索时间长、容易出现搜索停滞现象、数学基础还不完整。本文首先说明蚁群算法的基本思想,阐述了蚁群算法的原始模型及其特点，其次讨论如何利用遗传算法选取蚁群算法的参数，然后结合对边缘检测的蚁群算法具体实现过程进行研究分析，最后对本论文所做的工作进行全面总结,提出不足之处,并展望了今后要继续研究学习的工作内容。 关键词：蚁群算法;边缘检测;阈值;信息素;遗传算法; 1 前言 蚁群算法是近年来提出的一种群体智能仿生优化算法，是受到自然界中真实的蚂蚁群寻觅食物过程的启发而发现的。蚂蚁之所以能够找到蚁穴到食物之间的最短路径是因为它们的个体之间通过一种化学物质来传递信息，蚁群算法正是利用了真实蚁群的这种行为特征，解决了在离散系统中存在的一些寻优问题。该算法起源于意大利学者 Dorigo M 等人于 1991 年首先提出的一种基于种群寻优的启发式搜索算法，经观察发现，蚂蚁在寻找食物的过程中其自身能够将一种化学物质遗留在它们所经过的路径上，这种化学物质被学者们称为信息素。这种信息素能够沉积在路径表面，并且可以随着时间慢慢的挥发。在蚂蚁寻觅食物的过程中，蚂蚁会向着积累信息素多的方向移动，这样下去最终所有蚂蚁都会选择最短路径。该算法首先用于求解著名的旅行商问题（Traveling Salesman Problem，简称 TSP）并获得了较好的效果，随后该算法被用于求解组合优化、函数优化、系统辨识、机器人路径规划、数据挖掘、网络路由等问题。 尽管目前对 ACO 的研究刚刚起步，一些思想尚处于萌芽时期，但人们已隐隐约约认识到，人类诞生于大自然，解决问题的灵感似乎也应该来自大自然，因此越来越多人开始关注和研究 ACO，初步的研究结果已显示出该算法在求解复杂优化问题（特别是离散优化问题）方面的优越性。虽然 ACO 的严格理论基础尚未奠定，国内外的有关研究仍停留在实验探索阶段，但从当前的应用效果来看，这种自然生物的新型系统寻优思想无疑具有十分光明的前景。但该算法存在收敛速度慢且容易出现停滞现象的缺点，这是因为并不是所有的候选解都是最优解，而候选解却影响了蚂蚁的判断以及在蚂蚁群体中，单个蚂蚁的运动没有固定的规则，是随机的，蚂蚁与蚂蚁之间通过信息素来交换信息，但是对于较大规模的优化问题，这个信息传递和搜索过程比较繁琐，难以在较短的时间内找到一个最优的解。 由于依靠经验来选择蚁群参数存在复杂性和随机性,因此本文最后讨论如何利用遗传算法选取蚁群算法的参数。遗传算法得到的蚁群参数减少了人工选参的不确定性以及盲目性。 2 基本蚁群算法 2.1 蚁群算法基本原理 根据仿生学家的研究结果表明,单只蚂蚁不能找到从巢穴到食物源的最短路 径,而大量蚂蚁之间通过相互适应与协作组成的群体则可以,蚂蚁是没有视觉的,但是是通过蚂蚁在它经过的路径上留下一种彼此可以识别的物质,叫信息素,来相互传递信息,达到协作的。蚂蚁在搜索食物源的过程中,在所经过的路径上留下信息素,同时又可以感知并根据信息素的浓度来选择下一条路径,一条路径上的浓度越浓,蚂蚁选择该条路径的概率越大,并留下信息素使这条路径上的浓度加强,这样会有更多的蚂蚁选择次路径。相反,信息素浓度少的路
蚁群算法matlab精讲及仿真 4.1基本蚁群算法 4.1.1基本蚁群算法的原理 蚁群算法是上世纪90年代意大利学者M.Dorigo,v.Maneizz。等人提出来的,在越来越多的领域里得到广泛应用。蚁群算法，是一种模拟生物活动的智能算法，蚁群算法的运作机理来源于现实世界中蚂蚁的真实行为，该算法是由Marco Dorigo 首先提出并进行相关研究的，蚂蚁这种小生物，个体能力非常有限，但实际的活动中却可以搬动自己大几十倍的物体，其有序的合作能力可以与人类的集体完成浩大的工程非常相似，它们之前可以进行信息的交流，各自负责自己的任务，整个运作过程统一有序，在一只蚂蚁找食物的过程中，在自己走过的足迹上洒下某种物质，以传达信息给伙伴，吸引同伴向自己走过的路径上靠拢，当有一只蚂蚁找到食物后，它还可以沿着自己走过的路径返回，这样一来找到食物的蚂蚁走过的路径上信息传递物质的量就比较大，更多的蚂蚁就可能以更大的机率来选择这条路径，越来越多的蚂蚁都集中在这条路径上，蚂蚁就会成群结队在蚁窝与食物间的路径上工作。当然，信息传递物质会随着时间的推移而消失掉一部分，留下一部分，其含量是处于动态变化之中，起初，在没有蚂蚁找到食物的时候，其实所有从蚁窝出发的蚂蚁是保持一种随机的运动状态而进行食物搜索的，因此，这时，各蚂蚁间信息传递物质的参考其实是没有价值的，当有一只蚂蚁找到食物后，该蚂蚁一般就会向着出发地返回，这样，该蚂蚁来回一趟在自己的路径上留下的信息传递物质就相对较多，蚂蚁向着信息传递物质比较高的路径上运动，更多的蚂蚁就会选择找到食物的路径，而蚂蚁有时不一定向着信
息传递物质量高的路径走，可能搜索其它的路径。这样如果搜索到更短的路径后，蚂蚁又会往更短的路径上靠拢，最终多数蚂蚁在最短路径上工作。【基于蚁群算法和遗传算法的机器人路径规划研究】 该算法的特点： (1)自我组织能力，蚂蚁不需要知道整体环境信息，只需要得到自己周围的信息，并且通过信息传递物质来作用于周围的环境，根据其他蚂蚁的信息素来判断自己的路径。 (2)正反馈机制，蚂蚁在运动的过程中，收到其他蚂蚁的信息素影响，对于某路径上信息素越强的路径，其转向该路径的概率就越大，从而更容易使得蚁群寻找到最短的避障路径。 (3)易于与其他算法结合，现实中蚂蚁的工作过程简单，单位蚂蚁的任务也比较单一，因而蚁群算法的规则也比较简单，稳定性好，易于和其他算法结合使得避障路径规划效果更好。 (4)具有并行搜索能力探索过程彼此独立又相互影响，具备并行搜索能力，这样既可以保持解的多样性，又能够加速最优解的发现。 4.1.2 基本蚁群算法的生物仿真模型 a为蚂蚁所在洞穴,food为食物所在区,假设abde为一条路径,eadf为另外一条路径,蚂蚁走过后会留下信息素,5分钟后蚂蚁在两条路径上留下的信息素的量都为3,概率可以认为相同,而30分钟后baed路径上的信息素的量为60,明显大于eadf路径上的信息素的量。最终蚂蚁会完全选择abed这条最短路径,由此可见,
蚁群算法在物流系统优化中的应用 ——配送中心选址问题 LOGO https://www.doczj.com/doc/917779916.html,
框架 蚁群算法概述 蚁群算法模型 物流系统中配送中心选择问题 蚁群算法应用与物流配送中心选址 算法举例
蚁群算法简介 ?蚁群算法(Ant Algorithm简称AA)是近年来刚刚诞生的随机优化方法，它是一种源于大自然的新的仿生类算法。由意大利学者Dorigo最早提出，蚂蚁算法主要是通过蚂蚁群体之间的信息传递而达到寻优的目的，最初又称蚁群优化方法(Ant Colony Optimization简称ACO)。由于模拟仿真中使用了人工蚂蚁的概念，因此亦称蚂蚁系统(Ant System，简称AS)。
蚁群觅食图1 ?How do I incorporate my LOGO and URL to a slide that will apply to all the other slides? –On the [View]menu, point to [Master],and then click [Slide Master]or [Notes Master].Change images to the one you like, then it will apply to all the other slides. [ Image information in product ] ?Image : www.wizdata.co.kr ?Note to customers : This image has been licensed to be used within this PowerPoint template only. You may not extract the image for any other use.
第一章绪论 1.软件：是能够完成预定功能和性能的可执行的计算机诚信度。包括使程序正常执行所需的数据，以及有关描述程 序操作和使用的文档。即：软件 = 程序 + 文档 2.软件的特征：软件的开发不同于硬件设计、不同于硬件制造、不同于硬件维修。 3.软件工程方法学：把在软件生命周期全过程中使用的一整套技术方法的集合。三要素：方法、工具、过程 4.软件工程学的畴： 软件开发技术（软件开发方法学、软件工具、软件工程环境）、软件工程管理（软件管理学、软件经济学、度量学）。 5.软件工程：是指导计算机软件开发和维护的工程学科。它采用工程的概念、原理、技术和方法来开发与维护软件， 目的是为了实现按照预期的进度和经费完成软件生产计划，同时提高软件的生产率和可靠性。 6.软件的发展：大体经历了程序、软件、软件产品 3个阶段。 7.工具和方法是软件开发技术的2大支柱。 8.3种编程泛型：过程式编程泛型、面向对象编程泛型、基于构件技术的编程泛型 9.面向对象程序设计中，数据和操作被封装在一个对象中，对象之间则是通过消息相互联系。 10.构件：标准化/规格化的对象类。 11.3种编程泛型的差异: 粒度由小到大依次是：过程式编程式、面向对象编程式、基于构件的编程泛型。 12.软件工程的分化：1、传统软件工程2、面向对象软件工程3、基于构件的软件工程 13.消除软件危机的途径：①正确认识计算机软件；②充分认识到软件开发是一种组织良好、管理严密、各类人员协 同工作的工程项目；推广使用在实践中总结出来的开发软件的成功的技术和方法；③开发和使用更好的软件工具。第二章软件生存周期与软件过程 1.软件生存周期：计划、开发、运行3个时期。 需求分析-》软件分析-》软件设计-》编码测试-》软件测试-》运行维护 2.需求分析（用户视角）：功能需求、性能需求、环境约束、外部接口描述。 3.软件分析（开发人员视角）：建立与需求模型一致的，与实现无关的软件分析模型。 4.软件设计：总体设计/概要设计、详细设计（确定软件的数据结构和操作）。 5.软件测试：单元测试、集成测试、系统测试。 6.软件开发方法可区分：形式化方法、非形式化方法。 7.形式化开发模型：转换模型、净室模型
分子标记技术原理、方法及应用 一、遗传标记的类型及发展 遗传标记(genetic marker):指可追踪染色体、染色体某一节段、某个基因座在家系中传递的任何一种遗传特性。它具有两个基本特征，即可遗传性和可识别性；因此生物的任何有差异表型的基因突变型均可作为遗传标记。包括形态学标记、细胞学标记、生化标记和分子标记四种类型。 形态学标记：主要包括肉眼可见的外部形态特征，如：矮秆、紫鞘、卷叶等；也包括色素、生理特性、生殖特性、抗病虫性等有关的一些特性。优点: 形态学标记简单直观、经济方便。缺点: (1)数量在多数植物中是很有限的; (2) 多态性较差，表现易受环境影响; (3)有一些标记与不良性状连锁; (4)形态标记的获得需要通过诱变、分离纯合的过程，周期较长 细胞学标记：植物细胞染色体的变异：包括染色体核型（染色体数目、结构、随体有无、着丝粒位置等）和带型（C带、N带、G带等）的变化。优点: 能进行一些重要基因的染色体或染色体区域定位。缺点: (1)材料需要花费较大的人力和较长时间来培育，难度很大; (2) 有些变异难以用细胞学方法进行检测 生化标记：主要包括同工酶和等位酶标记。分析方法是从组织蛋白粗提物中通过电泳和组织化学染色法将酶的多种形式转变成肉眼可辩的酶谱带型。优点: 直接反映了基因产物差异，受环境影响较小。缺点: (1)目前可使用的生化标记数量还相当有限; (2)有些酶的染色方
法和电泳技术有一定难度 分子标记：主要指能反映生物个体或种群间基因组中某种差异特征的DNA片段，它直接反映基因组DNA间的差异，也叫DNA标记。 (1)数量多，高多态性，信息量大(2)与生长发育无关，取材不受限制(3)能明确辨别等位基因(4)均匀分布于整个基因组(5)选择中性，不影响目标性状的表达(6)检测手段简单、快速(7)成本低廉(8)稳定，重复性好(9)共显性遗传 在遗传学研究中广泛应用的DNA分子标记已经发展了很多种，一般依其所用的分子生物学技术大致可以分为三大类： 第一类是以分子杂交为核心的分子标记，包括RFLP、DNA指纹技术等，这类分子标记被称为第一代分子标记； 第二类是以PCR为核心的分子标记，包括随机扩增多态性RAPD、简单序列重复SSR、扩增片段长度多态性AFLP、序列标签位点STS等，为第二代分子标记； 第三类是一些新型的分子标记，如：SNP标记、表达序列标签EST 标记等，也以PCR技术为基础，为第三代分子标记。 几种主要的ＤＮＡ分子标记
2.1 蚁群算法的基本原理 蚁群优化算法是模拟蚂蚁觅食的原理，设计出的一种群集智能算法。蚂蚁在觅食过程中能够在其经过的路径上留下一种称之为信息素的物质，并在觅食过程中能够感知这种物质的强度，并指导自己行动方向，它们总是朝着该物质强度高的方向移动，因此大量蚂蚁组成的集体觅食就表现为一种对信息素的正反馈现象。某一条路径越短，路径上经过的蚂蚁越多，其信息素遗留的也就越多，信息素的浓度也就越高，蚂蚁选择这条路径的几率也就越高，由此构成的正反馈过程，从而逐渐的逼近最优路径，找到最优路径。 蚂蚁在觅食过程时，是以信息素作为媒介而间接进行信息交流，当蚂蚁从食物源走到蚁穴，或者从蚁穴走到食物源时，都会在经过的路径上释放信息素，从而形成了一条含有信息素的路径，蚂蚁可以感觉出路径上信息素浓度的大小，并且以较高的概率选择信息素浓度较高的路径。 (a) 蚁穴 1 2 食物源 A B (b) 人工蚂蚁的搜索主要包括三种智能行为： （1）蚂蚁的记忆行为。一只蚂蚁搜索过的路径在下次搜索时就不再被该蚂蚁选择，因此在蚁群算法中建立禁忌表进行模拟。 （2）蚂蚁利用信息素进行相互通信。蚂蚁在所选择的路径上会释放一种信息素的物质，当其他蚂蚁进行路径选择时，会根据路径上的信息素浓度进行选择，这样信息素就成为蚂蚁之间进行通信的媒介。 （3）蚂蚁的集群活动。通过一只蚂蚁的运动很难达到事物源，但整个蚁群进行搜索就完全不同。当某些路径上通过的蚂蚁越来越多时，路径上留下的信息素数量也就越多，导致信息素强度增大，蚂蚁选择该路径的概率随之增加，从而进一步增加该路径的信息素强度，而通过的蚂蚁比较少的路径上的信息素会随着时间的推移而挥发，从而变得越来越少。3.3.1蚂蚁系统 蚂蚁系统是最早的蚁群算法。其搜索过程大致如下： 在初始时刻，m 只蚂蚁随机放置于城市中， 各条路径上的信息素初始值相等，设为：0(0)ij ττ=为信息素初始值，可设0m m L τ=，m L 是由最近邻启发式方法构 造的路径长度。其次，蚂蚁(1,2,)k k m = ，按照随机比例规则选择下一步要转