遗传算法解决工作分配难题

难题：如今有10份工作。有300名职工被分派参加这10份工作，每一份工作中必须 30人。每个人参加不一样的工作中都是有个评使用价值，意味着该人参加该工作中的耗损值，耗损值的范畴在0-9。问：怎样分派这300人工作中，促使总的耗损值最少。

本难题的数据资料： 职工挑选工作中耗损表数据信息.rar

这是一个典型性的工作中分配问题。自然，运用匈牙利算法能求出该难题的最优解

今日，文中详细介绍运用细胞生物学优化算法来求得该工作中分配问题

下边先详细介绍些基本概念：

先给职工编个号，职工001-职工300

再给工作中编个号，工作中01-工作中10

个人案例：一个具体的分派计划方案被称作个人案例。比如：职工001-职工030参加工作中01、职工031-职工060参加工作中02、……、职工271-职工300参加工作中10。这就是一个个人案例。自然，个人案例的总的很有可能数十分多，要解析xml每一个个人案例并寻找最优解基本上不太可能。

案例权重值：每一个个人案例意味着一个具体分派计划方案，那麼该计划方案的全部职工的耗损值的总数——总的耗损值，便是该个人案例的案例权重值。求得最优解便是寻找案例权重值最少的那一个个人案例

遗传基因：每一个个人案例中，每一位职工挑选参加的工作中，称之为该个人案例的一个遗传基因。很显而易见，每一个个人案例有300个遗传基因，每一个遗传基因有10个挑选很有可能。遗传基因间有互相管束的功效（每一份工作中有且只有30人挑选，不可以多也不可以少）。给遗传基因编个号，遗传基因001-遗传基因300

繁殖：2个个人案例转化成一个新的个人案例的全过程称之为繁殖。2个个人案例称之为父代，新个人案例称之为后代。后代，从遗传基因001开始，任意从2个父代的遗传基因001中挑选一个，依次类推，直至遗传基因300截止。那样任意挑选300个遗传基因后，会造成一个新的难题——遗传基因矛盾，即一些总结会有超出30人，而一些总结会不够30人。再运用均衡优化算法开展案例內部的遗传基因调节，促使每一份工作中有且只有30人。那样的后代才算是合乎难题的个人案例。

基因变异：一个个人案例转化成一个新的个人案例的全过程称之为基因变异。一个个人案例称之为父代，新个人案例称之为后代。父代中任意选择N对遗传基因，互换这N对遗传基因，转化成后代（比如：挑选遗传基因033和遗传基因254，各自意味着职工033和职工254的挑选，互换她们的挑选，那样不容易造成遗传基因矛盾的难题）。

物种：多个个人案例构成一个物种。细胞生物学优化算法的关键便是搭建一个物种。物种里个人案例数要适合。不可以太少，太少了求得最优解的概率减少；不可以过多，尽管能提升 求得最优解的概率，可是也会大大增加求得的時间耗费。

迭代更新：物种演变的全过程称之为迭代更新。全过程以下：先在物种中选择一部分个人案例，根据繁殖转化成多个后代；再在物种中选择一部分个人案例，根据基因变异转化成多个后代。那样后代归于到物种中，物种中的总数就提升了，再对物种中的个人案例依照案例权重值开展挑选，取代掉一部分个人案例，以保持物种中的个人案例总数（有点像自然界的自然选择学说，适者生存？）。本难题中，依照案例权重值开展排列，保存案例权重值小的个人案例，取代掉案例权重值大的个人案例。

下边详细介绍怎样用细胞生物学优化算法求得本难题

搭建物种

先结构一个带有2000个个人案例的物种

每一个个人案例的建立全过程以下：先任意造成一个职工编码序列，随后依照职工编码序列，每一位职工都挑选当今对他而言耗损最少的工作中（最好挑选耗损为0的工作中，但倘若该工作中早已爆满了，就挑选耗损为1的工作中，依次类推）。很显而易见，最终一位职工仅有一种挑选。那样转化成的个人案例的案例权重值大概在85-140中间

开展迭代更新

每一次迭代更新，任意挑选父代繁殖出1000个后代，基因变异出一百个后代。那样父代和后代加在一起一共3一百个（2000 1000 100），随后对这3一百个个人案例依照案例权重值开展排列，保存权重值最少的2000个个人案例，1一百个个人案例淘汰掉，保存物种中2000个个人案例的总数平稳

之前提条件过，在繁殖的转化成的后代很有可能会出现遗传基因矛盾（一些总结会有超出30人，而一些总结会不够30人），必须 根据均衡优化算法开展案例內部的遗传基因调节，促使每一份工作中有且只有30人。下边详细介绍该均衡优化算法

1、 寻找超出30人的工作中，假定超出K人。若找不着，表明早已均衡，撤出优化算法

2、 寻找全部小于30人的工作中，记工作中集W

3、 在流程1中的每一位职工，测算出在工作中集W中全部工作中的耗损值的极小值，并纪录相匹配的工作中序号

4、 对流程1中的全部职工依照流程3中的极小值开展排列，取最少的前K人，分派到其所相匹配的工作上。那样确保流程1中的工作中就仅有30人了

5、 反复流程1

根据上边的迭代更新全过程，开展许多次迭代更新，在迭代更新完毕后，在物种中寻找案例权重值最少的个人案例便是该难题的最优解

那麼，怎么判断出早已获得最优解，来停止迭代更新全过程呢？有二种方式

一是，特定迭代更新频次，比如迭代更新1000次。

这一因为沒有基础理论支撑点，并不了解1000次能迭代更新到哪些程度，故不适合。

二是，每一次迭代更新后，都测算一下新的后代在物种中的数量。若持续许多次迭代更新（比如10次）新的后代在物种中的数量为0，那麼迭代更新完毕（表明迭代更新早已不可以造成新的个人案例了）

文中中，用的就是这个，下边把迭代更新全过程贴一下

迭代更新全过程：迭代更新全过程.rar

最优解：最优解.rar

续篇

细胞生物学优化算法能否寻找最优解？这一不一定的，看迭代更新的数据信息收敛了，可是能收敛性到一个部分最优解（贴近最优解或是便是最优解）。现阶段，根据几回的求得全过程，所获得的最优解是55，倘若有些人算出更优质解，热烈欢迎沟通交流

根据查询迭代更新数据信息，发觉，迭代更新完毕的情况下，物种中的个人案例的权重值全是55，也就是所有个人案例都一样了。