精华内容
下载资源
问答
  • 解决算法问题的五种通用方法
    千次阅读
    2013-10-21 20:56:23

              毫无疑问,解决算法问题一定不止5种方法,但是下面的五种方法可能更加有用。但是还是要记住,算法靠的是不停的练习,练习越多,很多问题就迎刃而解! 同样也必须记住,这五种方法不是单独的组成,它们可以混合在一起使用。也就是说,可能某一个算法的解决方法同时使用了下面两种方法。

              方法一:举例法

              描述:列举问题的例子,然后看看自己能不能计算出一个通用的答案

              例子:给定时钟上的某个时间,计算出时针和分针之间的形成的角度

              解决方法:首先举个例子,比如3:27,我们可以画一个简单的3时27分,两个针所形成的角度。通过多画出这个这样简单的例子,我们可以看到如下的规律:

                               (1)分针和12点方向之间形成的角度:360*minutes/60

                               (2)时针和12点方向之间形成的角度:360*(hours%12)/12+360*(minutes/60)*(1/12)

                               (3)时针和分针之间的角度:(hour angle - minute angle)  %360

            通过简单的算术运算,可以化简为 30*hours - 5.5*minutes


            方法二:相似问题联想

            描述:考虑遇到的这个问题和哪个问题比较相似,进而修改其解决方案来求解遇到的新的问题

            例子:将一个排序的数组进行旋转,比如说3、4、5、6、7、1、2,求解出这个数组中最小的元素

            相似的问题:(1)寻找一个数组中的最小的元素

                                    (2)寻找一个数组中的特定的元素(比如二分法)

            算法:在一个数组中寻找最小的元素并不是一个很难的问题,只需要遍历数组中所有的元素。但是如果用这个方法来解决上述问题时,题目中的排序我们就没有使用到。然而,二分法是应用很广泛的。但是二分法的条件是递增的,而本题中的数组则是旋转递增的,也就是先是递增,然后从最小的元素再开始递增,最小的元素就是那个转折点。就本题中的数字而言,当比较第一个元素和中间元素(3和6)的时候,可以看到这个范围中的元素还是递增的。这就意味着转折点一定在6的后面(或者3就是最小的元素,这个数组根本没有旋转)。我们可以继续利用二分法寻找,对于任何一个区间,如果左边的元素小于右边,则转折点不在其中,如果大于则在其中。


            方法三:简化

            描述:改变一个题目中的一个限制条件(数据类型,大小等)来简化问题,然后再来解决原来的问题。一旦找到了简化问题的解决方法,再来归纳原问题的解决方案。

            例子:统计一篇文章中单词出现的次数。

            简化:首先我们不先解决有单词组成的问题,而是由字母组成的情况。也就是想象一下我们将一个杂志按照一个个的字母来归类。

            算法:我们可以通过构造一个简单的数组,然后统计字母的个数的方式来解决这个简化的问题。数组中的每一个点对应一个字母。首先我们计算每一个字母在清单中出现的次数,然后通过浏览整个文章来查看是不是我们统计了整个文章的全部字母。

            当我们泛化这个算法得到一般问题的解决方案时,可以很容易的得到,我们可以像构造数组一样构造一个哈希表,每一个单词为一个元素并且统计出现的次数。


           方法四:

           描述:面对一个问题,首先解决一个最简单最基本的情况(比如只有一个元素的时候),然后试图两个,并且假设你已经得到了一个元素的解。然后试图三个,不要忘记你已经知道一个和两个时候的解。

           例子:设计一个算法打印一个字符串所有的排列情况。为了简化,假设所有的字符没有重复。

           测试字符串:abcdefg

           Case "a"  -->  {a}

           Case "ab"   -->  {ab,ba}

           Case   "abc"   -->{?}

            这是一个有趣的例子,如果我们已经有了P(“ab”)的答案,我们怎么产生P(“abc”)的答案呢?我们可以看到,增加的字母是“c”,所以我们只需要看c可能的位置。归纳如下:

            merge(c,ab)  --> {cab,acb,abc}

            merge(c,ba)   -->{aba,bca,bac}

            算法:使用一个递归算法,通过将字符串的最后一个字符和前面n-1个字符的答案进行求解,将最后一个元素放到可以放置的任何一个可能的位置产生答案。


            方法五:“数据结构风暴”

            描述:这种方法是简单的,但是也是很有效的,容易掌握的。就是在做题时将自己学到的每一个数据结构进行选择,然后找出能够使用本题答案的数据结构。

            例子:随机产生一组数并且存在可以可扩充的数组中,如何标记数组的中位数?

            数据结构头脑风暴: 

            >> 链表?--可能不是,因为链表在直接访问和排序方面的没有优势。

            >>数组?--但是我们已经有了一个数组,如果再将元素排序放到一个数组中,也许时间和空间复杂度不是很好。先放在这儿,如果没有更好的,我们再返回到这儿。

            >>二叉树? --这个是有可能的,因为二叉树在排序方面的性能很好。事实上,如果二叉树是完美平衡的,那么最顶上的元素就是最大的元素。但是,这里有个小问题,如果元素的个数是偶数个,中位数是最顶端两个元素的平均,而中间两个元素不可能同时位于最顶端,这是可能要考虑的情况,我们一会儿再来想这些细节。

            >>堆? --在基本的排序和查找最大最小元素的算法中,堆的性能非常的好。如果有两个堆,你就可以将一堆元素分成打一半的元素和小一半的元素。大一半的元素使用小根堆,这样大一半元素中的最小元素就在堆的最顶端。同样,小一半的元素使用大根堆,小一半的元素中最大的元素就在最顶端。使用这样的数据源结构,就将可能的中位数放在了两个堆的顶端。如果两个堆的元素不相同,你就可以迅速的将元素多的堆中将元素移到元素比较少的堆中。

             最后强调算法还是要多做题目,你所遇到的和处理的问题越多,在选择数据结构和算法的过程中就越灵活。


          




    更多相关内容
  • 用贪心算法解决0-1背包问题是算法界较为经典的一个问题,笔者尝试用一个python脚本,实现对输入的问题数据生成相应的最优结果。 贪心算法 贪心算法(greedy algorithm),又称贪婪法,是寻找最优解问题的常用方法。...

    贪心算法与0-1背包问题

    用贪心算法解决0-1背包问题是算法界较为经典的一个问题,笔者尝试用一个python脚本,实现对输入的问题数据生成相应的最优结果。

    贪心算法

    贪心算法(greedy algorithm),又称贪婪法,是寻找最优解问题的常用方法。这种方法一般将求解过程分成若干个步骤在每个步骤都应用贪心原则,选取当前状态下最好的或最优的选择(局部最有利的选择),并以此希望最后堆叠出的结果也是最好或最优的解。贪婪法的每次决策都以当前情况为基础并根据某个最优原则进行选择,不从整体上考虑其他各种可能的情况。

    贪婪法和动态规划法以及分治法一样,都需要对问题进行分解,定义最优解的字结构,但是贪婪法与其他方法最大的不同在于,贪婪法每一步选择完之后,局部最优解就确定了,不再进行回溯处理,直到算法结束。因此,贪婪法只有在很少的情况下可以得到真正的最优解,比如最短路径问题、图的最小生成树问题。大多数情况下,由于选择策略的“短视”,贪婪法会错过真正的最优解,得不到问题的真正答案。但是贪婪法简单高效,省去了为找最优解可能需要的穷举操作,可以得到与最优解比较接近的近似最优解,通常作为其他算法的辅助算法使用。

    贪婪法的基本设计思想有以下三个步骤:
    (1)建立对问题精确描述的数学模型,包括定义最优解的模型
    (2)将问题分解为一系列子问题,同时定义子问题的最优解结构。
    (3)应用贪心原则确定每个子问题的局部最优解,并根据最优解的模型,用子问题的局部最优解堆叠出全局最优解。

    定义最优解的模型通常和定义子问题的最优解结构是同时进行的,最优解的模型一般都体现了最优解子问题的分解结构和堆叠方式。对于子问题的分解有多种方式,有的问题可以按照问题的求解过程一步一步地进行分解,每一步都在前一步的基础上选择当前最好的解,每做一次选择就将问题简化为一个规模更小的问题,当最后一步的求解完成后就得到了全局最优解。还有的问题可以将问题分解成相对独立的几个子问题,对每个子问题求解完成后再按照一定的规则将其组合起来得到全局最优解。

    0-1背包问题

    有N件物品和一个承重为C的背包,每件物品重量是wi, 价值是pi, 求解将哪几件物品装入背包可使这些物品的重量总和不超过C的情况下价值总和最大。
    背包问题(knapsack problem)是此类组合优化的NP问题的统称,比如货箱装载问题、货船载物问题等,因问题最初来源于如何选择最合适的物品装在背包中而得名。这个问题隐含了一个条件,每个物品只有一件,也就是限定每件物品只能选择0个或1个,因此又被称为0-1背包问题。

    解决策略

    在这个问题中,常见的贪婪策略有三种。第一种是根据物品的重量选择,每次都选重量最低的物品。第二种是根据物品的价值选择,每次都选价值最高的物品。第三种是定义一个价值密度的概念,每次都选择重量最轻的物品,将价值密度si定义为pi/wi
    笔者在这个python脚本文件中将三种策略都封装进函数,取得各自的结果后,再比较所得总价值,最终输出价值最高的一种结果。

    算法实现

    笔者利用几个封装的函数,在主程序中分别调用后得出结果。

    初始化函数

    根据输入选择是否使用默认的一组数据进行演示,把重量、价值和总重量分别存入weight、price和C,并打印出来以供核对。

    def Initial():
    	'''确定物品重量、价值和背包总重量'''
    	option = input('是否选择使用默认数据(Y/N): ')
    	if option == 'Y':
    		weight = [35, 30, 60, 50, 40, 10, 25]
    		price = [10, 40, 30, 50, 35, 40, 30]
    		C = 150
    	else:
    		weight = list(map(int, input('请输入物品重量,用空格分开:').split( )))
    		price = list(map(int, input('请输入相应的物品价值,用空格分开: ').split( )))
    		C = int(input('请输入背包总重量限制: '))
    	item = list(zip(weight,price))
    	print('重量,价值:' + item.__str__() + '\n总重量限制:' + C.__str__())
    	return item, C
    

    三种策略

    分别用三个函数实现了三种选择策略,函数最终返回的结果是按照相应选择方法对物品排序后的索引值,以供算法函数使用。

    def Weight(item):
    	'''选重量最小的物品'''
    	data = np.array(item)
    	idex = np.lexsort([-1*data[:,1], data[:,0]])
    	return idex
    
    def Price(item):
    	'''选价值最大的物品'''	
    	data = np.array(item)
    	idex = np.lexsort([data[:,0], -1*data[:,1]])
    	return idex
    
    def Density(item):
    	'''选价值密度最大的物品'''
    	number = len(item)
    	data = np.array(item)
    	data_list = [0] * number
    	for i in range(number):
    		data_list[i] = (data[i,1])/(data[i,0])
    	data_set = np.array(data_list)
    	idex = np.argsort(-1*data_set)
    	return idex
    

    贪心算法

    贪心算法函数实现了具体的问题解决过程,用初始化的数据和索引值作为参数,计算后返回一组最优化选择的结果。

    def GreedyAlgo(item, C, idex):
    	'''贪心算法'''
    	number = len(item)
    	status = [0] * number
    	total_weight = 0
    	total_value = 0
    	for i in range(number):
    		if item[idex[i],0] <= C:
    			total_weight += item[idex[i],0]
    			total_value += item[idex[i],1]
    			status[idex[i]] = 1
    			C -= item[idex[i],0]
    		else:
    			continue
    	return total_weight, total_value, status
    

    比较函数

    比较用三种策略计算后得到结果中总价值的大小,并返回价值最高的一组结果。

    def Compare(total_value1, total_value2, total_value3):
    	'''比较三种结果'''
    	values = zip(total_value1, total_value2, total_value3)
    	data = np.array([total_value1[1], total_value2[1], total_value3[1]])
    	idex = np.argsort(data)
    	value = list(zip(*values))
    	results = list(value[idex[2]])
    	return results
    

    主函数

    主函数通过调用以上几个函数,最终实现问题的解决方案,并打印出最优结果,同时打印出三种策略各自的最优结果,以供检查。

    def main():
    	'''主体结构'''
    	item0, C = Initial()
    	item = np.array(item0)
    	idex_weight = Weight(item)
    	idex_price = Price(item)
    	idex_Density = Density(item)
    	results_weight = GreedyAlgo(item, C, idex_weight)
    	print(results_weight)
    	results_Price = GreedyAlgo(item, C, idex_price)
    	print(results_Price)
    	results_Density = GreedyAlgo(item, C, idex_Density)
    	print(results_Density)
    	results = Compare(results_weight, results_Price, results_Density)
    	print(results)
    

    脚本文件

    python脚本文件中,除了上述几个函数,还有两行代码以以实现运行。

    import numpy as np
    
    main()
    

    运行

    以上,代码就全部编写完成了,下面来看看脚本文件在fish中运行的结果。
    贪心算法python脚本在fish运行结果
    如图,fish中显示了使用默认数据集和手动输入的数据集运行的两种结果。

    结语

    笔者第一次发博,代码和算法都很生疏,还存在很多问题,望广大网友多多批评指正,共同进步!

    致谢

    整个过程从社区中学习到了很多,感谢广大网友。
    主要参考内容:
    [1]《算法的乐趣》——王晓华
    [2]https://blog.csdn.net/sunny1235435/article/details/95603969.

    展开全文
  • 文章目录禁忌搜索算法解决路线规划问题问题定义CVRP问题解决算法禁忌搜索...车辆路线规划问题一个经典的组合优化问题,也是旅行商问题的泛化。该问题的定义为: 有给定数量的客户有运输需求; 为从某个固定地点出...

    禁忌搜索算法解决路线规划问题

    问题定义

    车辆路线规划问题是一个经典的组合优化问题,也是旅行商问题的泛化。该问题的定义为:

    • 有给定数量的客户有运输需求;
    • 为从某个固定地点出发和返回的车辆寻找一个最优路线试的可以服务所有的客户
      车辆路线规划问题是NP-hard问题,一般建议求最优解的近似解。

    车辆路线规划问题有很多变种,主要包含 Classical VRP(VRP)、 Capacitated Vehicle Routing Problem (CVRP)、 Vehicle Routing Problem with Time Windows (VRPTW)、 Vehicle Routing Problem with Pick-Up and Delivery (VRPPD)等。现实生活中VRP模型用处较少,其它都很常见;CVRP对应配送中心对配送站点的送货,VRPTW则面向客户的送货,如外卖;VRPPD对应取货和送货,如京东快递即可以送快递又可以取快递。

    本本主要套餐CVRP,其定义如下:

    令G =(V,A)表示一个有向图,其中V是顶点集,而A是弧集。一个顶点表示 m个容量为Q的相同车辆组成的车队所在的仓库,其它顶点表示要服务的客户。每个客户顶点vi与需求qi关联。每个弧(vi,vj)通过A与耗费成本cij相关联。 CVRP目标是找到一系列路线,以便:

    • 每条路线以仓库为起始点;
    • 每个用户仅被服务一次;
    • 每条路线的需求量不超过Q;
    • 所有路线总消耗成本最小;

    CVRP问题解决算法

    本文使用贪心算法(Greedy Algorithm)初始解决方案,使用禁忌搜索算法(Tabu Search Algorithm)进行优化并求得最优解;测试用例来源为http://vrp.atd-lab.inf.puc-rio.br/index.php/en/

    禁忌搜索算法

    禁忌搜索算法是一种应用局部搜索的启发式搜索算法;

    局部搜索的两种策略

    1)选定一个可行的初始解,定义邻域。从邻域中找到最好的解与初始解比较,然后取最小的解为新的初始解。如此迭代直到解满足一定条件后停止。
    2)随机法。从初始可行解邻域中随机选择一点,与初始解比较,循环直到解的质量达到一定程度。

    局部搜索的缺点

    1)无法保证得到全局最优解。
    2)解的质量依赖于起始点和领域的选取。
    3)为了得到高质量的解,需要比较不同的邻域结构和初始解,只有在选择足够多时,才能保证得到最优解。

    禁忌搜索算法的提出

    禁忌搜索(Tabu Search)是局部领域算法的推广,Fred Glover Fred Glover在1986年提出这个概念,进而进一步形成一套完整的算法。算法的特点就是禁忌,禁止重复前面的工作,跳出局部最优点。

    禁忌搜索算法流程图

    在这里插入图片描述

    禁忌搜索算法伪码

         1 sBest ← s0
         2 bestCandidate ← s0
         3 tabuList ← []
         4 tabuList.push(s0)
         5 while (not stoppingCondition())
         6 	sNeighborhood ← getNeighbors(bestCandidate)
         7 	bestCandidate ← sNeighborHood.firstElement
         8 	for (sCandidate in sNeighborHood)
         9 		if ( (not tabuList.contains(sCandidate)) and (fitness(sCandidate) > fitness(bestCandidate)) )
        10 			bestCandidate ← sCandidate
        11 		end
        12 	end
        13 	if (fitness(bestCandidate) > fitness(sBest))
        14 		sBest ← bestCandidate
        15 	end
        16 	tabuList.push(bestCandidate)
        17 	if (tabuList.size > maxTabuSize)
        18 		tabuList.removeFirst()
        19 	end
        20 end
        21 return sBest
    

    算法结果

    统计结果

    实例客户数采用禁忌搜索算法前.采用禁忌搜索算法后用例目前最优解
    A-n32-k532903.7787.08784
    A-n60-k9601464.091362.381408
    A-n80-k10801845.081828.281764
    B-n78-k10781421.761315.221266
    P-n101-k4101771.68715.89681

    详细结果

    使用禁忌搜索算法解决CVRP部分结果如下,测试用例来源为Capacitated Vehicle Routing Problem Library

    • A-n32-k5
      Vehicle 1: 1(0)->13(21)->2(19)->17(18)->31(14)->1(0) totalDemand = 72.0
      Vehicle 2: 1(0)->28(20)->25(24)->1(0) totalDemand = 44.0
      Vehicle 3: 1(0)->22(12)->32(9)->20(24)->18(19)->14(16)->8(16)->27(2)->1(0) totalDemand = 98.0
      Vehicle 4: 1(0)->7(12)->4(6)->3(21)->24(8)->5(19)->12(14)->29(15)->15(3)->1(0) totalDemand = 98.0
      Vehicle 5: 1(0)->21(8)->6(7)->26(24)->11(8)->30(2)->16(22)->23(4)->10(16)->9(6)->19(1)->1(0) totalDemand = 98.0
      最优解: 787.08

    • A-n60-k9
      Vehicle 1: 1(0)->42(21)->34(6)->39(14)->60(23)->53(18)->1(0) totalDemand = 82.0
      Vehicle 2: 1(0)->17(11)->21(1)->4(7)->12(19)->41(11)->47(1)->26(18)->1(0) totalDemand = 68.0
      Vehicle 3: 1(0)->35(9)->25(24)->59(9)->24(23)->48(17)->15(13)->1(0) totalDemand = 95.0
      Vehicle 4: 1(0)->36(5)->56(9)->51(4)->40(19)->27(19)->18(24)->28(2)->30(17)->1(0) totalDemand = 99.0
      Vehicle 5: 1(0)->5(11)->22(5)->54(21)->31(9)->50(2)->45(18)->29(17)->7(17)->1(0) totalDemand = 100.0
      Vehicle 6: 1(0)->19(2)->8(21)->14(20)->38(2)->58(22)->9(23)->20(3)->1(0) totalDemand = 93.0
      Vehicle 7: 1(0)->3(2)->2(16)->49(42)->23(20)->37(9)->32(11)->1(0) totalDemand = 100.0
      Vehicle 8: 1(0)->16(5)->44(21)->57(18)->13(18)->52(24)->10(10)->33(2)->1(0) totalDemand = 98.0
      Vehicle 9: 1(0)->11(6)->55(11)->6(9)->43(20)->46(48)->1(0) totalDemand = 94.0
      最优解: 1362.38

    • A-n80-k10
      Vehicle 1: 1(0)->50(13)->37(12)->39(23)->67(11)->68(5)->74(12)->1(0) totalDemand = 76.0
      Vehicle 2: 1(0)->2(24)->8(26)->22(13)->41(13)->1(0) totalDemand = 76.0
      Vehicle 3: 1(0)->59(7)->77(14)->33(9)->46(23)->5(5)->23(26)->51(10)->71(5)->1(0) totalDemand = 99.0
      Vehicle 4: 1(0)->14(12)->75(19)->30(10)->18(20)->32(2)->60(22)->28(4)->6(11)->1(0) totalDemand = 100.0
      Vehicle 5: 1(0)->11(9)->72(12)->64(22)->63(18)->24(17)->45(6)->13(16)->1(0) totalDemand = 100.0
      Vehicle 6: 1(0)->54(13)->4(23)->61(13)->40(21)->78(2)->43(23)->1(0) totalDemand = 95.0
      Vehicle 7: 1(0)->73(2)->55(2)->10(23)->56(14)->57(7)->70(9)->66(2)->36(2)->27(4)->48(2)->20(12)->76(6)->21(15)->1(0) totalDemand = 100.0
      Vehicle 8: 1(0)->52(3)->65(6)->34(1)->16(2)->42(13)->47(11)->26(12)->58(21)->62(22)->31(9)->1(0) totalDemand = 100.0
      Vehicle 9: 1(0)->35(2)->3(22)->38(14)->9(9)->44(3)->17(6)->69(9)->79(2)->7(23)->25(7)->1(0) totalDemand = 97.0
      Vehicle 10: 1(0)->12(14)->53(6)->29(20)->80(24)->49(7)->19(26)->15(2)->1(0) totalDemand = 99.0

    最优解: 1828.28

    • B-n78-k10
      Vehicle 1: 1(0)->18(6)->73(12)->59(3)->22(5)->25(3)->53(23)->2(14)->1(0) totalDemand = 66.0
      Vehicle 2: 1(0)->39(14)->70(12)->44(11)->68(14)->57(9)->28(23)->3(17)->1(0) totalDemand = 100.0
      Vehicle 3: 1(0)->66(13)->76(4)->38(14)->71(23)->31(4)->6(19)->64(20)->1(0) totalDemand = 97.0
      Vehicle 4: 1(0)->78(19)->24(4)->45(21)->27(4)->12(2)->65(5)->41(5)->54(25)->1(0) totalDemand = 85.0
      Vehicle 5: 1(0)->50(12)->30(21)->74(15)->77(23)->8(5)->58(21)->48(2)->1(0) totalDemand = 99.0
      Vehicle 6: 1(0)->9(12)->13(26)->16(18)->52(14)->33(6)->21(14)->55(8)->1(0) totalDemand = 98.0
      Vehicle 7: 1(0)->43(14)->26(15)->11(2)->69(16)->19(18)->17(6)->67(6)->61(6)->7(17)->1(0) totalDemand = 100.0
      Vehicle 8: 1(0)->72(5)->23(9)->35(4)->47(18)->46(20)->32(1)->4(17)->63(22)->1(0) totalDemand = 96.0
      Vehicle 9: 1(0)->51(22)->62(2)->40(26)->49(19)->75(21)->29(7)->1(0) totalDemand = 97.0
      Vehicle 10: 1(0)->42(2)->15(7)->37(5)->5(16)->60(22)->36(20)->56(3)->34(16)->14(2)->20(2)->10(4)->1(0) totalDemand = 99.0

    最优解: 1315.22

    • P-n101-k4
      Vehicle 1: 1(0)->54(14)->59(18)->41(9)->22(11)->74(9)->73(25)->75(8)->76(18)->57(6)->5(19)->55(18)->81(6)->69(36)->78(14)->4(13)->80(23)->34(11)->82(26)->10(16)->52(10)->51(13)->77(13)->13(19)->27(17)->29(16)->1(0) totalDemand = 388.0
      Vehicle 2: 1(0)->53(9)->8(5)->83(16)->49(36)->20(17)->48(27)->47(1)->37(5)->50(30)->65(9)->12(12)->64(10)->91(3)->33(23)->11(16)->63(19)->89(9)->32(27)->28(16)->1(0) totalDemand = 290.0
      Vehicle 3: 1(0)->95(27)->7(3)->97(11)->100(9)->60(28)->94(22)->86(41)->101(17)->92(1)->45(18)->15(20)->39(16)->87(35)->17(19)->62(13)->6(26)->85(7)->18(2)->46(16)->9(9)->84(11)->61(3)->19(12)->90(15)->1(0) totalDemand = 381.0
      Vehicle 4: 1(0)->14(23)->96(20)->93(2)->99(10)->38(8)->98(12)->88(26)->43(5)->44(7)->16(8)->58(7)->3(7)->42(5)->23(18)->24(29)->68(25)->40(31)->26(6)->56(2)->25(3)->30(9)->79(3)->35(14)->36(8)->72(15)->66(20)->67(25)->21(9)->31(21)->71(5)->2(10)->70(6)->1(0) totalDemand = 399.0

    最优解: 715.89

    结论

    1. 禁忌搜索是解决路线规划问题的优秀算法
    2. 无法保证一定能获得最优解,这取决与具体问题参数选择,一般执行次数越多效果约好

    代码清单

    读取测试数据

    public class VRPLibReader {
    
        private InstanceReader reader;
    
        private int dimension;
        private int vehicleCapacity;
        private double[][] coord;
        private double[][] distance;
        private int[] demand;
        private double[][] pickup;
        private LocalTime[][] timeWindows;
        private int[] standTime;
        private int[] depots;
    
        public VRPLibReader(InstanceReader reader) {
            this.reader = reader;
    
            readHeader();
            readCoordinates();
            readDemand();
            convertCoordToDistance();
        }
    
        private void readHeader() {
            String line = reader.readLine();
    
            while (!line.equalsIgnoreCase("NODE_COORD_SECTION")) {
                String[] split = line.split(":");
    
                String key = split[0].trim();
    
                if (key.equalsIgnoreCase("DIMENSION")) {
                    dimension = Integer.valueOf(split[1].trim());
                }
    
                if (key.equalsIgnoreCase("CAPACITY")) {
                    vehicleCapacity = Integer.valueOf(split[1].trim());
                }
    
                line = reader.readLine();
    
                if (line == null) {
                    break;
                }
            }
        }
    
        private void readCoordinates() {
            coord = new double[dimension][2];
    
            String line = reader.readLine();
            while (!line.equalsIgnoreCase("DEMAND_SECTION")) {
                parseRow(line, coord);
    
                line = reader.readLine();
            }
        }
    
        private void parseRow(String line, double[][] coord) {
            String[] split = line.split("\\s+");
    
            int i = Integer.valueOf(split[0].trim()) - 1;
            coord[i][0] = Double.valueOf(split[1].trim());
            coord[i][1] = Double.valueOf(split[2].trim());
        }
    
        private void readDemand() {
            demand = new int[dimension];
    
            String line = reader.readLine();
            while (!line.equalsIgnoreCase("DEPOT_SECTION")) {
    
                String[] split = line.split("\\s+");
    
                int i = Integer.valueOf(split[0].trim()) - 1;
                demand[i] = Integer.valueOf(split[1].trim());
    
                line = reader.readLine();
            }
        }
    
        private void readPickup() {
            pickup = new double[dimension][2];
    
            String line = reader.readLine();
            while (!line.equalsIgnoreCase("TIME_WINDOW_SECTION")) {
                parseRow(line, pickup);
    
                line = reader.readLine();
            }
        }
    
        private void readTimeWindows() {
            timeWindows = new LocalTime[dimension][2];
    
            String line = reader.readLine();
            while (!line.equalsIgnoreCase("STANDTIME_SECTION")) {
                String[] split = line.split("\\s+");
    
                int i = Integer.valueOf(split[0].trim()) - 1;
    
                String startTime = split[1].trim();
                String endTime = split[2].trim();
                if (startTime.equals("")) {
                    startTime = "0" + split[2].trim();
                    endTime = split[3].trim();
    
                    if (endTime.equals("")) {
                        endTime = "0" + split[4].trim();
                    }
                }
    
                timeWindows[i][0] = LocalTime.parse(startTime);
                timeWindows[i][1] = LocalTime.parse(endTime);
    
                line = reader.readLine();
            }
        }
    
        private void readStandtime() {
            standTime = new int[dimension];
    
            String line = reader.readLine();
            while (!line.equalsIgnoreCase("DEPOT_SECTION")) {
                String[] split = line.split("\\s+");
    
                int i = Integer.valueOf(split[0].trim()) - 1;
                standTime[i] = Integer.valueOf(split[1].trim());
    
                line = reader.readLine();
            }
        }
    
        private void readDepots() {
            depots = new int[2];
    
            String line = reader.readLine();
            int i = 0;
            while (!line.equalsIgnoreCase("EOF")) {
                depots[i] = Double.valueOf(line.trim()).intValue();
                i++;
    
                line = reader.readLine();
            }
        }
    
        private void convertCoordToDistance() {
            distance = new double[dimension][dimension];
    
            for (int i = 0; i < dimension; i++) {
                for (int j = i; j < dimension; j++) {
                    if (i != j) {
                        double x1 = coord[i][0];
                        double y1 = coord[i][1];
                        double x2 = coord[j][0];
                        double y2 = coord[j][1];
    
                        distance[i][j] = euclideanDistance(x1, y1, x2, y2);
                        distance[j][i] = distance[i][j];
                    }
                }
            }
        }
    
        private static double euclideanDistance(double x1, double y1, double x2, double y2) {
            double xDistance = Math.abs(x1 - x2);
            double yDistance = Math.abs(y1 - y2);
    
            return Math.sqrt(Math.pow(xDistance, 2) + Math.pow(yDistance, 2));
        }
    
        public int getDimension() {
            return dimension;
        }
    
        public double[][] getDistance() {
            return distance;
        }
    
        public int getVehicleCapacity() {
            return vehicleCapacity;
        }
    
        public int[] getDemand() {
            return demand;
        }
    
        public int[] getDepots() {
            return depots;
        }
    
        private static final double EARTH_RADIUS = 6371.393; // 平均半径,单位:km
    
        /**
         * 通过AB点经纬度获取距离
         * @return 距离(单位:米)
         */
        public static double getDistance(double x1, double y1, double x2, double y2) {
            // 经纬度(角度)转弧度。弧度用作参数,以调用Math.cos和Math.sin
            double radiansAX = Math.toRadians(y1); // A经弧度
            double radiansAY = Math.toRadians(x1); // A纬弧度
            double radiansBX = Math.toRadians(y2); // B经弧度
            double radiansBY = Math.toRadians(x2); // B纬弧度
    
            // 公式中“cosβ1cosβ2cos(α1-α2)+sinβ1sinβ2”的部分,得到∠AOB的cos值
            double cos = Math.cos(radiansAY) * Math.cos(radiansBY) * Math.cos(radiansAX - radiansBX)
                    + Math.sin(radiansAY) * Math.sin(radiansBY);
            double acos = Math.acos(cos); // 反余弦值
            return EARTH_RADIUS * acos; // 最终结果
    
        }
    }
    
    

    初始解

    public class GreedySolver {
        private final int noOfVehicles;
        private final Node[] nodes;
        private final double[][] distances;
        private final int noOfCustomers;
        private final Vehicle[] vehicles;
    
        private double cost;
    
        public GreedySolver(VRPRunner jct) throws IOException {
            VRPLibReader reader = new VRPLibReader(new InstanceReader(new File(jct.instance)));
            this.noOfCustomers = reader.getDimension();
            this.noOfVehicles = reader.getDimension();
            this.distances = reader.getDistance();
            this.cost = 0;
    
            nodes = new Node[noOfCustomers];
    
            for (int i = 0; i < noOfCustomers; i++) {
                nodes[i] = new Node(i, reader.getDemand()[i]);
            }
    
            this.vehicles = new Vehicle[this.noOfVehicles];
    
            for (int i = 0; i < this.noOfVehicles; i++) {
                vehicles[i] = new Vehicle(reader.getVehicleCapacity());
            }
        }
    
        private boolean unassignedCustomerExists(Node[] Nodes) {
            for (int i = 1; i < Nodes.length; i++) {
                if (!Nodes[i].IsRouted)
                    return true;
            }
            return false;
        }
    
        public GreedySolver solve() {
            double CandCost, EndCost;
            int VehIndex = 0;
    
            while (unassignedCustomerExists(nodes)) {
                int CustIndex = 0;
                Node Candidate = null;
                double minCost = (float) Double.MAX_VALUE;
    
                if (vehicles[VehIndex].routes.isEmpty()) {
                    vehicles[VehIndex].AddNode(nodes[0]);
                    if(!nodes[CustIndex].IsRouted) {
                        nodes[CustIndex].IsRouted = true;  //不会被当成真实节点
                    }
    
                }
    
                for (int i = 0; i < noOfCustomers; i++) {
                    if (!nodes[i].IsRouted) {
                        if (vehicles[VehIndex].initCheckIfFits(nodes[i].demand)) {
                            CandCost = distances[vehicles[VehIndex].currentLocation][i];
                            if (minCost > CandCost) {
                                minCost = CandCost;
                                CustIndex = i;
                                Candidate = nodes[i];
                            }
                        }
                    }
                }
    
                if (Candidate == null) {
                    //Not a single Customer Fits
                    if (VehIndex + 1 < vehicles.length) //We have more vehicles to assign
                    {
                        if (vehicles[VehIndex].currentLocation != 0) {//End this route
                            EndCost = distances[vehicles[VehIndex].currentLocation][0];
                            vehicles[VehIndex].AddNode(nodes[0]);
                            this.cost += EndCost;
                        }
                        VehIndex = VehIndex + 1; //Go to next Vehicle
                    } else //We DO NOT have any more vehicle to assign. The problem is unsolved under these parameters
                    {
                        System.out.println("\nThe rest customers do not fit in any Vehicle\n" +
                                "The problem cannot be resolved under these constrains");
                        System.exit(0);
                    }
                } else {
                    vehicles[VehIndex].AddNode(Candidate);//If a fitting Customer is Found
                    nodes[CustIndex].IsRouted = true;
                    this.cost += minCost;
                }
            }
    
            EndCost = distances[vehicles[VehIndex].currentLocation][0];
            vehicles[VehIndex].AddNode(nodes[0]);
            this.cost += EndCost;
    
            return this;
        }
    
        public void print() {
            System.out.println("=========================================================");
    
            for (int j = 0; j < noOfVehicles; j++) {
                if (!vehicles[j].routes.isEmpty()) {
                    System.out.print("Vehicle " + j + ":");
                    int RoutSize = vehicles[j].routes.size();
                    for (int k = 0; k < RoutSize; k++) {
                        if (k == RoutSize - 1) {
                            System.out.print(vehicles[j].routes.get(k).NodeId);
                        } else {
                            System.out.print(vehicles[j].routes.get(k).NodeId + "->");
                        }
                    }
                    System.out.println();
                }
            }
            System.out.println("\nBest Value: " + this.cost + "\n");
        }
    
        public Vehicle[] getVehicles() {
            return vehicles;
        }
    
        public double getCost() {
            return cost;
        }
    }
    
    

    禁忌搜索解法

    public class TabuSearchSolver {
    
        private final double[][] distances;
        private final int noOfVehicles;
        private final int TABU_Horizon;
        private final int iterations;
        private final Vehicle[] BestSolutionVehicles;
    
        private Vehicle[] vehicles;
        private double cost;
    
        private double BestSolutionCost;
    
        public TabuSearchSolver(VRPRunner jct) throws IOException {
            VRPLibReader reader = new VRPLibReader(new InstanceReader(new File(jct.instance)));
            this.noOfVehicles = reader.getDimension();
            this.TABU_Horizon = jct.TabuHorizon;
            this.distances = reader.getDistance();
            this.iterations = jct.iterations;
    
            GreedySolver greedySolver = new GreedySolver(jct);
            greedySolver.solve();
            this.vehicles = greedySolver.getVehicles();
            this.cost = greedySolver.getCost();
    
            this.BestSolutionVehicles = new Vehicle[this.noOfVehicles];
    
            for (int i = 0; i < this.noOfVehicles; i++) {
                this.BestSolutionVehicles[i] = new Vehicle(reader.getRealVehicleCapacity(i), i + 1);
            }
        }
    
        public TabuSearchSolver solve() {
            //We use 1-0 exchange move
            ArrayList<Node> routesFrom;
            ArrayList<Node> routesTo;
    
            int MovingNodeDemand = 0;
    
            int VehIndexFrom, VehIndexTo;
            double BestNCost, NeighborCost;
    
            int SwapIndexA = -1, SwapIndexB = -1, SwapRouteFrom = -1, SwapRouteTo = -1;
            int iteration_number = 0;
    
            int DimensionCustomer = this.distances[1].length;
            int TABU_Matrix[][] = new int[DimensionCustomer + 1][DimensionCustomer + 1];
    
            this.BestSolutionCost = this.cost;
    
            while (iteration_number < iterations) {
                BestNCost = Double.MAX_VALUE;
    
                for (VehIndexFrom = 0; VehIndexFrom < this.vehicles.length; VehIndexFrom++) {
                    routesFrom = this.vehicles[VehIndexFrom].routes;
                    int RoutFromLength = routesFrom.size();
    
                    for (int i = 1; i < (RoutFromLength - 1); i++) { //Not possible to move depot!
    
                        for (VehIndexTo = 0; VehIndexTo < this.vehicles.length; VehIndexTo++) {
                            routesTo = this.vehicles[VehIndexTo].routes;
                            int RouteToLength = routesTo.size();
                            for (int j = 0; (j < RouteToLength - 1); j++) {//Not possible to move after last Depot!
    
                                MovingNodeDemand = routesFrom.get(i).demand;
    
                                if ((VehIndexFrom == VehIndexTo) || this.vehicles[VehIndexTo].CheckIfFits(MovingNodeDemand)) {
                                    //If we assign to a different route check capacity constrains
                                    //if in the new route is the same no need to check for capacity
    
                                    if (!((VehIndexFrom == VehIndexTo) && ((j == i) || (j == i - 1))))  // Not a move that Changes solution cost
                                    {
                                        // minnus length after remove from fromRouting, and insert into to toRouting
                                        double MinusCost1 = this.distances[routesFrom.get(i - 1).NodeId][routesFrom.get(i).NodeId];
                                        double MinusCost2 = this.distances[routesFrom.get(i).NodeId][routesFrom.get(i + 1).NodeId];
                                        double MinusCost3 = this.distances[routesTo.get(j).NodeId][routesTo.get(j + 1).NodeId];
    
                                        // add length after remove from fromRouting, and insert into to toRouting
                                        double AddedCost1 = this.distances[routesFrom.get(i - 1).NodeId][routesFrom.get(i + 1).NodeId];
                                        double AddedCost2 = this.distances[routesTo.get(j).NodeId][routesFrom.get(i).NodeId];
                                        double AddedCost3 = this.distances[routesFrom.get(i).NodeId][routesTo.get(j + 1).NodeId];
    
                                        //Check if the move is a Tabu! - If it is Tabu break
                                        if ((TABU_Matrix[routesFrom.get(i - 1).NodeId][routesFrom.get(i + 1).NodeId] != 0)
                                            || (TABU_Matrix[routesTo.get(j).NodeId][routesFrom.get(i).NodeId] != 0)
                                            || (TABU_Matrix[routesFrom.get(i).NodeId][routesTo.get(j + 1).NodeId] != 0)) {
                                            break;
                                        }
    
                                        NeighborCost = AddedCost1 + AddedCost2 + AddedCost3
                                            - MinusCost1 - MinusCost2 - MinusCost3;
    
                                        // ensure the solution is valid
                                        if (NeighborCost < BestNCost) {
                                            BestNCost = NeighborCost;
                                            SwapIndexA = i;
                                            SwapIndexB = j;
                                            SwapRouteFrom = VehIndexFrom;
                                            SwapRouteTo = VehIndexTo;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
    
                for (int o = 0; o < TABU_Matrix[0].length; o++) {
                    for (int p = 0; p < TABU_Matrix[0].length; p++) {
                        if (TABU_Matrix[o][p] > 0) {
                            TABU_Matrix[o][p]--;
                        }
                    }
                }
    
                routesFrom = this.vehicles[SwapRouteFrom].routes;
                routesTo = this.vehicles[SwapRouteTo].routes;
                this.vehicles[SwapRouteFrom].routes = null;
                this.vehicles[SwapRouteTo].routes = null;
    
                Node SwapNode = routesFrom.get(SwapIndexA);
    
                int NodeIDBefore = routesFrom.get(SwapIndexA - 1).NodeId;
                int NodeIDAfter = routesFrom.get(SwapIndexA + 1).NodeId;
                int NodeID_F = routesTo.get(SwapIndexB).NodeId;
                int NodeID_G = routesTo.get(SwapIndexB + 1).NodeId;
    
                Random TabuRan = new Random();
                int randomDelay1 = TabuRan.nextInt(5);
                int randomDelay2 = TabuRan.nextInt(5);
                int randomDelay3 = TabuRan.nextInt(5);
    
                TABU_Matrix[NodeIDBefore][SwapNode.NodeId] = this.TABU_Horizon + randomDelay1;
                TABU_Matrix[SwapNode.NodeId][NodeIDAfter] = this.TABU_Horizon + randomDelay2;
                TABU_Matrix[NodeID_F][NodeID_G] = this.TABU_Horizon + randomDelay3;
    
                routesFrom.remove(SwapIndexA);
    
                if (SwapRouteFrom == SwapRouteTo) {
                    if (SwapIndexA < SwapIndexB) {
                        routesTo.add(SwapIndexB, SwapNode);
                    } else {
                        routesTo.add(SwapIndexB + 1, SwapNode);
                    }
                } else {
                    routesTo.add(SwapIndexB + 1, SwapNode);
                }
    
                // update vehicle load
                this.vehicles[SwapRouteFrom].routes = routesFrom;
                this.vehicles[SwapRouteFrom].load -= SwapNode.demand;
    
                this.vehicles[SwapRouteTo].routes = routesTo;
                this.vehicles[SwapRouteTo].load += SwapNode.demand;
    
                this.cost += BestNCost;
    
                if (this.cost < this.BestSolutionCost) {
                    iteration_number = 0;
                    this.SaveBestSolution();
                } else {
                    iteration_number++;
                }
            }
    
            this.vehicles = this.BestSolutionVehicles;
            this.cost = this.BestSolutionCost;
    
            return this;
        }
    
        public boolean exceedMaxLoad(List<Node> nodes, int capacity) {
            double vechileTotalDemand = 0;
            for (Node node : nodes) {
                vechileTotalDemand += node.demand;
            }
            return vechileTotalDemand > capacity;
        }
    
        private void SaveBestSolution() {
            this.BestSolutionCost = this.cost;
            for (int j = 0; j < this.noOfVehicles; j++) {
                this.BestSolutionVehicles[j].routes.clear();
                if (!this.vehicles[j].routes.isEmpty()) {
                    int RoutSize = this.vehicles[j].routes.size();
                    for (int k = 0; k < RoutSize; k++) {
                        Node n = this.vehicles[j].routes.get(k);
                        this.BestSolutionVehicles[j].routes.add(n);
                    }
                }
            }
        }
    
        public void print() {
            System.out.println("==========================the result===============================");
            for (int j = 0; j < this.noOfVehicles; j++) {
                if (!this.vehicles[j].routes.isEmpty() && this.vehicles[j].routes.size() > 2) {
                    System.out.print("Vehicle " + this.vehicles[j].vehicleNum + ": ");
                    int RoutSize = this.vehicles[j].routes.size();
                    for (int k = 0; k < RoutSize; k++) {
                        Node node = this.vehicles[j].routes.get(k);
                        if (k == RoutSize - 1) {
                            System.out.print((node.NodeId + 1) + "(" + node.demand + ")");
                        } else {
                            System.out.print((node.NodeId) + 1 + "(" + node.demand + ")" + "->");
                        }
                    }
                    System.out.println(" totalDemand = " + getDemand(this.vehicles[j].routes));
                }
            }
            System.out.println("\nBest Value: " + this.cost + "\n");
        }
    
        private double getDemand(List<Node> nodes) {
            double vechileTotalDemand = 0;
            for (Node node : nodes) {
                vechileTotalDemand += node.demand;
            }
            return vechileTotalDemand;
        }
    }
    

    程序入口

    public class VRPRunner {
        @Parameter(names = {"--algorithm", "-alg"}, required = true)
        private String alg = "tabu";
        @Parameter(names = {"--instance", "-i"})
        public String instance = "datasets/big/Golden_20.vrp";
        @Parameter(names = "--iterations")
        public int iterations = 1000;
        @Parameter(names = "--tabu")
        public Integer TabuHorizon = 10;
    
        public static void main(String[] args) throws IOException {
            VRPRunner jct = new VRPRunner();
            JCommander jCommander = new JCommander(jct);
            jCommander.setProgramName(VRPRunner.class.getSimpleName());
    
            switch (jct.alg) {
                case "tabu": {
                    new TabuSearchSolver(jct)
                            .solve()
                            .print();
                    break;
                }
                default:
                case "greedy": {
                    new GreedySolver(jct)
                            .solve()
                            .print();
                    break;
                }
            }
        }
    }
    
    展开全文
  • 遗传算法解决01背包问题

    万次阅读 2018-06-18 15:57:38
    遗传算法求解01背包问题一、问题描述01背包问题属于组合优化问题一个例子,求解01背包问题的过程可以被视作在很多可行解当中求解一个最优解。01背包问题的一般描述如下:给定n个物品和一个背包,物品i的重量为Wi,...

    遗传算法求解01背包问题

    一、问题描述

    01背包问题属于组合优化问题的一个例子,求解01背包问题的过程可以被视作在很多可行解当中求解一个最优解。01背包问题的一般描述如下:

    给定n个物品和一个背包,物品i的重量为Wi,其价值为Vi,背包的容量为C。选择合适的物品装入背包,使得背包中装入的物品的总价值最大。注意的一点是,背包内的物品的重量之和不能大于背包的容量C在选择装入背包的物品时,对每种物品i只有两种选择:装入背包或者不装入背包,即只能将物品i装入背包一次。称此类问题为0/1背包问题。

    01背包问题是NP问题,传统的解决方法有动态规划法、分支界限法、回溯法等等。传统的方法不能有效地解决01背包问题。遗传算法(Genetic Algorithms)则是一种适合于在大量的可行解中搜索最优(或次优)解的有效算法。

    二、遗传算法

    1、遗传算法的基本思想

    遗传算法的搜索从一个被称作种群的候选解集开始,新的种群由旧的种群中产生以期得到更好的种群。从旧种群中按照解的适应度来选择解以产生新的解;适应度越大,解被选择生成后代的机率也越大。这个从已有种群中选择双亲并产生后代的迭代过程持续到遗传算法的停止条件满足为止。

    2、遗传算法的基本元素。

    遗传算法由以下几个原素组成:由染色体组成的种群,根据适应度进行选择以及交叉产生后代。

    三、用遗传算法求解01背包问题

    1、01背包问题中染色体的表示。

    用向量X来表示染色体,

    X = x1x2……,xn}。,xi∈{0,1},

    xi=1表示物品i装入了背包,xi =0表示物品i未装入背包。

    每个染色体对应其当前装入背包的物品的总价值和总重量。背包中物品的中价值代表了该物品的适应度。

    程序中定义了这样的一个结构来表示染色体:

    typedef struct{

    int Weight; //染色体代表的物品的总重量

    int Fitness; //染色体代表的物品的价值(适应度)

    int Gene[NUMG]; //用元素取值于定义域{0,1}的数组表示染色体。

    }GENE;

    2、遗传算法求解01背包问题时用到的参数。

    POPSIZE:种群大小,即已知的可行解的个数。

    NUMG:染色体中基因的个数,即物品的总数。

    CAPACITY:背包的容量。

    MAXB:二进制表示的染色体换算之后的最大十进制整数。用于随机产生一个整数,进而转换作染色体。

    SIM:染色体之间的相似度阈值。当染色体之间的相似度达到阈值时,算法即停止运行。

    PC=1.0 :交叉概率为100%。

    PM=0.2 :变异概率为20%,变异可以保证种群的多样性,从而防止算法收敛于某个局部解。

    3、选择操作。

    选择操作采用了赌轮选择(Roulette-wheel selection)的方法。函数selectIndex()中包含了选择染色体的具体过程。其流程图如图1所示。

     

    1 赌轮选择流程图

    程序中用一个Begin来代表当前赌轮上的指针的位置,End则用来使赌轮循环转动。

    summaryBE表示当前赌轮上的指针转过的染色体的总价值。

    summaryF表示当前全部染色体的价值总和。

    用randProb作为染色体选择的阈值。randProb为介于[0,1]之间的随机数。

    选择使summaryBE/summaryF 大于阈值randProb的染色体作为要选择的染色体。

    4、交叉操作

    程序中采用了单点交叉的策略。如下程序代码所示:

    for(int j=0; j<partPos ;j++){

    nextGenome[i].Gene[j] = parentGenome[Father].Gene[j];

    nextGenome[i+POPSIZE/2].Gene[j] = parentGenome[Mother].Gene[j];

    }

    for(;j<NUMG;j++){

    nextGenome[i].Gene[j] = parentGenome[Father].Gene[j];

    nextGenome[i+POPSIZE/2].Gene[j] = parentGenome[Mother].Gene[j];

    }

    partPos为随机产生的整数,代表交叉的位置。第一个for循环将partPos位置之前的基因遗传给一个后代,而第二个循环则将partPos位置之后的基因进行了交换。

    calculateCapacity函数用于计算交叉操作后的染色体的容量。

    calculateFitness函数用于计算交叉操作后的染色体的适应度。

    checkCapacity函数则用于检查交叉后的染色体的合理性,容量超出背包的染色体是不合理的。这里没有使后代死亡,而是随机地调整了染色体中的基因。使得基因能够适应环境(背包的容量)而继续生存。

    5、精英策略

    精英策略为了不使最优解在交叉的过程中,不会丢失最优解而采取的策略。其思想是保存上一代中的适应性强的染色体。相应地取代下一代中适应性弱的染色体。

    程序中精英策略由keepBestParents函数和sortFiness函数来实现。需要说明的是sortFitness仅仅对种群的索引进行了排序。然后用父代中20%的适应度较大的优秀染色体替换子代中20%的适应性弱的染色体。

    6、变异操作

    染色体的变异可以保持种群的多样性,防止最优解的丢失以及算法收敛到局部最优解。

    变异操作由mutation函数实现。

    首先产生一个介于01之间的随机数prob,若prob小于MP则进行变异操作:随机产生一个位置partPos,然后变异前染色体的partPos位置的基因为1,则变异为0,否则变异为1;相应地要进行适应度和染色体容量的变化。

    7、代际更新

    代际之间的更新,即用新生成的种群代替取代旧的种群。这个操作在updateGeneration函数中实现,同时这个操作使用了前面提及的精英策略。实际上,父代种群中优秀的染色体已被保留,updateGeneration中只是用新种群中的优秀染色体来代替父代中的染色体。

    由于对父代和子代的染色体都进行了排序,因此程序中将子代的80%视作优秀,将父代中的前20%视作优秀。

    8、算法的终止

    程序中采用了一个HASH表来对子代种群的适应度进行HASH操作。HASH表中的头结点纪录了头结点所指向的单链表的信息。如下代码中的注释:

    typedef struct Head{

    int maxFitness;   //单链表中的最大的Fitness

    int Count; //HASH到该结点的染色体的数目

    int Diff; //单链表中有多少不同的Fitness

    HASHNODE *Next;

    }HEAD;

    用这样的一个HASH表结构可以只需遍历HASH表中的头结点,即可知当前的种群的适应度最大的染色体是否集中。

    具体地,如checkFitness函数中的下面几行代码:

    index = maxFitness(hashTable);

    double CPount = hashTable[index].Count/(double)POPSIZE;

    double pDiff = hashTable[index].Diff/(double)POPSIZE;

    if(CPount>=0.9 && pDiff<=0.1){

    sameFlag = false;

    }

    如果当前maxFitness最大的头结点满足if语句中的判断条件,则sameFlag置为真,即算法停止迭代的条件得到了满足。

    TraverseHashTable函数则用于遍历HASH表。

    算法终止的另一个条件是迭代的次数。程序中设定了算法的最大迭代次数为1000

    四、实验结果。

    试验中用到的物品的重量和价值分别存储于以下两个数组之中。

    int Weight[NUMG]={6,9,8,8,6, 1, 10,5,7, 1};

    int Value[NUMG]={2,20,5,4,19,14,18,8,11,6};

    父代种群存储于parentGenome[NUMG]中,子代种群存储于nextGenome[NUMG]中。程序的初始状态和结束状态如下面的表格所示:

    初始的种群

    Weight

    Value

    染色体中的基因

    21

    52

    0010110101

    22

    23

    0011000101

    22

    40

    0001100011

    22

    53

    0100010110

    26

    45

    1010011001

    24

    53

    1100010011

    22

    53

    0100010110

    23

    25

    1011010000

    26

    48

    1010110100

    25

    29

    0111000000

    初始的HASH

    头结点索引

    maxFitness

    Count

    Diff

    单链表中的结点内容

    0

    52

    1

    1

    52:

    1

    53

    4

    2

    53:40:

    3

    29

    1

    1

    29:

    6

    45

    1

    1

    45:

    9

    48

    1

    1

    48:

    10

    23

    1

    1

    23:

    12

    25

    1

    1

    25:

    程序在运行了16次后停止运行。

    停止时的种群

    Weight

    Value

    染色体中的基因

    29

    78

    0100110111

    29

    78

    0100110111

    29

    78

    0100110111

    29

    78

    0100110111

    29

    78

    0100110111

    29

    78

    0100110111

    29

    78

    0100110111

    28

    64

    0100100111

    29

    78

    0100110111

    29

    78

    0100110111

    停止时的HASH

    头结点索引

    maxFitness

    Count

    Diff

    单链表中的结点内容

    0

    78

    9

    1

    78:

    12

    64

    1

    1

    64:

    即可知当前01背包问题的最优解为

    X =0,1,0,0,1,1,0,1,1,1}

    对应的最优值是78,即当前能够装入背包的最大价值。

    展开全文
  • 第7-6课:遗传算法的两应用实例

    千次阅读 2020-09-22 12:16:54
    所谓的确定性是指以上这些算法都是建立在确定性基础上的搜索算法,在搜索过程中遇到一个决策点时,对于选 a 还是选 b,其结果是确定的。比如贪婪法,就是按照贪婪策略选择,同样的条件下,每个决策选 1000 次结果都...
  • 雪花算法是twitter提出的分布式id生成器方案,但是有三个问题,其中前两个问题在业内很常见: 时间回拨问题 机器id的分配和回收问题 机器id的上限问题 Butterfly(蝴蝶)是一个超高性能的发号器框架。起名...
  • 遗传算法求解背包问题

    万次阅读 多人点赞 2017-12-26 21:03:28
    enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列,同时列出数据和数据下标,一般用在 for 循环当中。 enumerate(sequence, [start=0]): sequence – 一个序列、迭代器或...
  • 算法和数据结构》学习路线指引

    万次阅读 多人点赞 2021-07-01 11:16:15
    前 WorldFinal 选手对学习算法的一点总结。五张思维导图解决你的困惑
  • 我的第算法

    万次阅读 2019-01-18 23:30:40
    481 张步骤图详解 26 个算法和 7 数据结构的基本原理 没有枯燥的理论和复杂的代码,易于理解 采用大量彩色图片,清晰直观,便于记忆 零基础也能轻松掌握,自学算法的好搭档 作者简介 石田保辉,自由职业...
  • 以下来自百度百科:遗传算法的基本运算过程如下:a)初始化:设置进化代数计数器t=0,设置最大进化代数T,随机生成M个体作为初始群体P(0)。b)个体评价:计算群体P(t)中各个个体的适应度。c)选择运算:将选择算子作用...
  • 算法应该怎么“玩”?

    千次阅读 2018-11-06 11:49:00
    市面上关于算法的书可谓琳琅满目,有经典但难啃的、也有简单入门的、更有独辟蹊径的,不过这些大多数都是偏理论的多、偏应用的少,很多读者啃完后,对各种排序、搜索、遍历等常用算法了如指掌,但是遇到实际问题时...
  • 遗传算法) 遗传算法的基本原理

    万次阅读 多人点赞 2020-02-03 22:25:13
    遗传算法)遗传算法的基本原理 1.概述 遗传算法(Genetic Algorithm, GA)起源于对生物系统所进行的计算机模拟研究。它是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法,借鉴了达尔文的进化论和...
  • Python数据结构与算法(1.7)——算法分析

    万次阅读 多人点赞 2021-11-07 15:52:58
    我们已经知道算法是具有有限步骤的过程,其最终的目的是为了解决问题,而根据我们的经验,同一个问题解决方法通常并非唯一。这就产生一个有趣的问题:如何对比用于解决同一问题的不同算法?为了以合理的方式提高...
  • 编程算法同步入门

    千次阅读 2019-05-29 23:30:03
    如果软件的功能非常简单,一个软件也可以只有一个程序。 理论上讲,其实很多全部功能都安装部署在一台机器上的软件(单机版软件),都可以把所有功能写在一个程序里。 但是在现实当中我们会故意不这样做。原因是,复杂...
  • Paxos算法原理和过程解析

    万次阅读 多人点赞 2019-06-19 15:27:50
    Google Chubby的作者Mike Burrows说过,世上只有一种一致性算法,那就是Paxos,所有其他一致性算法都是Paxos算法的不完整版。Paxos算法是公认的晦涩,很难可能能将清楚,但是工程上也很难实现,所以有很多Paxos算法...
  • 优化算法综述

    千次阅读 2021-06-30 21:21:03
    依据 分类 具体算法 分类名 全局优化 遗传算法(GA)、帝国竞争算法(ICA)、 粒子群优化(PSO) 局部优化 模拟退火(SA)、贪婪算法(Greedy)、 邻域搜索(NS) 是否精确算法 精确算法 ...
  • 算法设计与分析重点总结

    千次阅读 多人点赞 2021-01-02 20:26:23
    算法就是解决问题的方法,是解决某一特定问题的一组有穷指令的序列,是完成一个任务所需要的具体步骤和方法 2.算法的特征 有限性 一个算法总是在执行了有穷步的运算之后终止 确定性:算法的每种运算必须要有确切的...
  • 怎么去思考一个问题,提高解决问题的能力 前言: #:本文转发自【半路歌雨】 #:http://blog.jboost.cn/think-like-a-programmer.html #:如有侵权,联系即删 技术人员的价值,不在于你能写出多么优美的代码,也不...
  • 完整整理了4种分布式共识算法(拜占庭容错算法)的原理,包括PBFT、PoW、PoS、DPos
  • Apriori算法--关联分析算法

    万次阅读 多人点赞 2017-10-16 15:49:49
    在实际生产生活我们经常会遇到一些“关联分析”(Association Analyse)的任务。举几实际例子。1.人们的购物清单里面的各个商品有没有什么...我们怎么从份购物清单里面发现这种往往会一起出现的商品组合呢?2.现在
  • 03 Q-Learning介绍 Q-Learning是Value-Based的强化学习算法,所以算法里面有一个非常重要的Value就是Q-Value,也是Q-Learning叫法的由来。这里重新把强化学习的五个基本部分介绍一下。 Agent(智能体): 强化学习...
  • 算法和数据结构》算法零基础五十题讲解

    万次阅读 多人点赞 2021-10-02 10:52:03
    「 让天下没有难学的算法
  • 聚类算法综述()

    万次阅读 2018-12-09 09:55:49
    前面介绍的基本K均值存在一个问题:如果所有的点在指派步骤都未分配到某个簇,就会得到空簇。如果这种情况发生,则需要某种策略来选择一个替补质心,否则的话,平方误差将会偏大。一种方法是选择一个距离当前任何...
  • 遗传算法(Genetic Algorithm, GA)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是种通过模拟自然进化过程搜索最优解的方法。 其主要特点是直接对结构对象进行操作,不存在求导和函数...
  • 贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。贪心算法(自我理解) 将整体求解拆分成局部求解...
  • 主宰操作系统的经典算法

    万次阅读 多人点赞 2020-07-24 15:22:50
    此篇文章带你梳理一下操作系统中都...如果只有一个 CPU 可用,那么必须选择接下来哪个进程/线程可以运行。操作系统中有一个叫做 调度程序(scheduler) 的角色存在,它就是做这件事儿的,调度程序使用的算法叫做 调度算
  • 2019-06-25 19:43:14 朴素贝叶斯: 1. 如果给出的特征向量长度可能不同,这是需要归一化为通长度的向量(这里以文本分类为例),比如说是句子单词的话,则长度为整个词汇量的长度,...其中项条件概率可以...
  • 数据结构与算法学习笔记

    万次阅读 多人点赞 2018-09-25 13:55:49
    数据结构指的是“组数据的存储结构”,算法指的是“操作数据的组方法”。 数据结构是为算法服务的,算法是要作用再特定的数据结构上的。 最常用的数据结构预算法: 数据结构:数组、链表、栈、队列、散列表、...
  • 算法之美

    千次阅读 2018-08-14 00:44:39
    内容简介 我们所有人的生活都受到有限空间和有限时间...这些看似是人类特有的难题,其实不然,因为计算机也面临同样的问题,计算机科学家几十年来也一直在努力解决这些问题,而他们找到的解决方案可以给我们很多启发...
  • 多任务进化优化算法()——多因子进化算法(MFEA)

    万次阅读 多人点赞 2019-10-25 19:09:21
    最近看了很多关于多任务优化的文章,觉得这是一个蛮有意思的方向,想把里面最经典的两个方法介绍给大家,今天先介绍第一个MFEA,这个方向有一个平台,这里面有原作者的代码及最新的出版物,感兴...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 204,895
精华内容 81,958
关键字:

解决某个具体问题的算法只有一个