Python程序开发教程.pptVIP

代价函数代价函数的选取是优化算法的重要环节。本例中，可以综合考虑如下因素来构造代价函数：价格：所有航班的总票价旅行时间：所有人在飞机上度过的总时间等待时间：在机场等待其他成员到达的总时间出发时间：早晨太早起飞的航班有额外的代价，因为旅行者睡眠不足汽车租用时间：如果集体租车，那么他们最好在某个时间前将车归还，否则会多付租金。代价函数限于篇幅，就不给出代价函数的全部代码了，使用方法如下：reload(optimization)optimization.schedulecost(s)5285有了代价函数，下面就是找到具有最小函数值的方案了。在这个例子中有16个航班、每个航班都有9种可能，所有的可能数为916,约3000亿，所以穷举是不现实的。下面使用两种方法实现优化： 随机优化 爬山法随机优化随机生成一些方案，找出其中最好的方案。defrandomoptimize(domain,costf): best=999999999 bestr=None foriinrange(1000): #随机生成一个方案 r=[random.randint(domain[i][0],domain[i][1]) foriinrange(len(domain))] #计算代价 cost=costf(r) #与当前最优方案的代价比较 ifcostbest: best=cost bestr=r returnr爬山法随机优化的不足在于，没有充分利用已有的优解。爬山法则以一个随机解开始，然后在邻近的解集中寻找更好的解，这类似于从斜坡上往下走，如图。下面的代码片段描述了如何获取已有解的邻近解:neighbors=[]forjinrange(len(domain)): #两个方向 ifsol[j]domain[j][0]: neighbors.append(sol[0:j]+[sol[j]+1]+sol[j+1:]) ifsol[j]domain[j][1]: neighbors.append(sol[0:j]+[sol[j]-1]+sol[j+1:])爬山法爬山法虽然利用了已经找到的优解，但它很容易陷入所谓的局部最优解，而找不到全局最优解。一种改进是随机重复爬山法，即从多个随机点开始运行爬山法若干次，以此希望有一个解能逼近全局最小。此外，模拟退火算法和遗传算法也能避免陷入局部最小值。查看结果在交互控制台中输入如下代码，查看优化结果：reload(optimization)domain=[(0,8)]*(len(optimization.people)*2)s=optimization.randomoptimize(domain,optimization.schedulecost)optimization.schedulecost(s)3328optimization.printschedule(s)SeymourBoston12:34-15:02$10912:08-14:05$142FrannyDallas12:19-15:25$3429:49-13:51$229ZooeyAkron9:15-12:14$24715:50-18:45$243WaltMiami15:34-18:11$32614:08-16:09$232BuddyChicago14:22-16:32$12615:04-17:23$189LesOmaha15:03-16:42$1356:19-8:13$239查看结果s=optimization.hillclimb(domain,optimization.schedulecost)optimization.schedulecost(s)3063optimization.printschedule(s)SeymourBOS12:34-15:02$10910:33-12:03$74FrannyDAL10:30-14:57$29010:51-14:16$256ZooeyCAK10:53-13:36$18910:32-13:16$139WaltMIA11:28-14:40$24812:37-15:05$170BuddyORD12:44-14:17$13410:33-13:11$132LesOMA11:08-13:07$17518:25-20:34$205总结 在本例中，首先使用Py