利用遗传学算法求解工作分配问题
问题:现在有10份工作。有300名工人被分配参与这10份工作,每份工作需要30人。每人参与不同的工作都有个评价值,代表该人参与该工作的损耗值,损耗值的范围在0-9。问:如何分配这300人工作,使得总的损耗值最低。
本问题的基础数据: 工人选择工作损耗表数据.rar
这是一个典型的工作分配问题。当然,利用匈牙利算法能求出该问题的最优解
今天,本文介绍利用遗传学算法来求解该工作分配问题
下面先介绍些名词解释:
先给工人编个号,工人001-工人300
再给工作编个号,工作01-工作10
个体实例:一个实际的分配方案被称为个体实例。例如:工人001-工人030参与工作01、工人031-工人060参与工作02、……、工人271-工人300参与工作10。这就是一个个体实例。当然,个体实例的总的可能数非常多,要遍历每个个体实例并找到最优解几乎不可能。
实例权重:每个个体实例代表一个实际分配方案,那么该方案的所有工人的损耗值的总和——总的损耗值,就是该个体实例的实例权重。求解最优解就是找到实例权重最小的那个个体实例
基因:每个个体实例中,每一位工人选择参与的工作,称为该个体实例的一个基因。很显然,每个个体实例有300个基因,每个基因有10个选择可能。基因间有相互约束的作用(每份工作有且只有30人选择,不能多也不能少)。给基因编个号,基因001-基因300
繁衍:两个个体实例生成一个新的个体实例的过程称为繁衍。两个个体实例称为父代,新个体实例称为子代。子代,从基因001开始,随机从两个父代的基因001中选择一个,依次类推,直到基因300为止。这样随机选择300个基因后,会产生一个新的问题——基因冲突,即某些工作会有超过30人,而某些工作会不足30人。再利用平衡算法进行实例内部的基因调整,使得每份工作有且只有30人。这样的子代才是符合问题的个体实例。
变异:一个个体实例生成一个新的个体实例的过程称为变异。一个个体实例称为父代,新个体实例称为子代。父代中随机选取N对基因,对换这N对基因,生成子代(例如:选择基因033和基因254,分别代表工人033和工人254的选择,交换他们的选择,这样不会产生基因冲突的问题)。
种群:若干个个体实例组成一个种群。遗传学算法的核心就是构建一个种群。种群里个体实例数要合适。不能太少,太少了求解最优解的可能性降低;不能太多,虽然能提高求解最优解的可能性,但是也会大大增加求解的时间消耗。
迭代:种群进化的过程称为迭代。过程如下:先在种群中选取部分个体实例,通过繁衍生成若干子代;再在种群中选取部分个体实例,通过变异生成若干子代。这样子代归入到种群中,种群中的数量就增加了,再对种群中的个体实例按照实例权重进行选择,淘汰掉部分个体实例,以维持种群中的个体实例数量(像不像大自然的自然选择,优胜劣汰?)。本问题中,按照实例权重进行排序,保留实例权重小的个体实例,淘汰掉实例权重大的个体实例。
下面介绍如何用遗传学算法求解本问题
构建种群
先构造一个含有2000个个体实例的种群
每个个体实例的创建过程如下:先随机产生一个工人序列,然后按照工人序列,每位工人都选择当前对他来说损耗最小的工作(最好是选择损耗为0的工作,但假如该工作已经满员了,就选择损耗为1的工作,依次类推)。很显然,最后一位工人只有一种选择。这样生成的个体实例的实例权重大约在85-140之间
进行迭代
每次迭代,随机选择父代繁衍出1000个子代,变异出100个子代。这样父代和子代加在一起一共3100个(2000+1000+100),然后对这3100个个体实例按照实例权重进行排序,保留权重最低的2000个个体实例,1100个个体实例被淘汰掉,保留种群中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,也就是全部个体实例都一样了。
相关文章
- Google瓦片地图算法解析
- Java实现 蓝桥杯VIP 算法训练 新生舞会
- Java实现 蓝桥杯 算法训练 动态数组使用
- 谱聚类算法及其代码(Spectral Clustering)
- 教你用Python实现简单监督学习算法
- 简单易学的机器学习算法—SVD奇异值分解
- 一步步教你轻松学朴素贝叶斯模型算法理论篇1
- 数据结构与算法-5 数据库索引 B+树 [MD]
- ML之prophet:利用prophet算法对上海最高气温实现回归预测(时间序列的趋势/周季节性趋势/年季节性趋势)案例
- XAI之ALE:基于titanic泰坦尼克数据集对RF算法利用ALE累积局部效应图可视化算法进而实现模型可解释性案例
- ML之Hash_EditDistance:基于输入图片哈希化(均值哈希+差值哈希)即8*8个元素的单向vector利用编辑距离算法实现计算图像相似度案例
- ML之PySpark:基于PySpark框架针对adult人口普查收入数据集结合Pipeline利用LoR/DT/RF算法(网格搜索+交叉验证评估+特征重要性)实现二分类预测(年收入是否超50k)案例
- ML之prophet:利用prophet算法对维基百科页面的日志每日页面浏览量实现回归预测(时间序列的趋势/周季节性趋势/年季节性趋势)案例
- ML之LoR:基于信用卡数据集利用LoR逻辑回归算法实现如何开发通用信用风险评分卡模型之以scorecardpy框架全流程讲解
- ML之xgboost:利用xgboost算法(自带方式)训练mushroom蘑菇数据集(22+1,6513+1611)来预测蘑菇是否毒性(二分类预测)
- ML之回归预测之Lasso:利用Lasso算法对对红酒品质wine数据集解决回归(实数值评分预测)问题—优化模型【增加新(组合)属性】
- ML之分类预测:基于sklearn库的七八种机器学习算法利用糖尿病(diabetes)数据集(8→1)实现二分类预测
- DL之LSTM:基于《wonderland爱丽丝梦游仙境记》小说数据集利用LSTM算法(层加深,基于keras)对单个character字符预测
- DL之RNN:人工智能为你写诗——基于TF利用RNN算法实现【机器为你写诗】、训练&测试过程全记录
- ML之回归预测:利用十类机器学习算法(线性回归、kNN、SVM、决策树、随机森林、极端随机树、SGD、提升树、LightGBM、XGBoost)对波士顿数据集回归预测(模型评估、推理并导到csv)
- ML之NB:利用朴素贝叶斯NB算法(CountVectorizer+不去除停用词)对fetch_20newsgroups数据集(20类新闻文本)进行分类预测、评估
- ML之KG:基于MovieLens电影评分数据集利用基于知识图谱的推荐算法(networkx+基于路径相似度的方法)实现对用户进行Top电影推荐案例
- Keras之DNN:利用DNN算法【Input(8)→12+8(relu)→O(sigmoid)】利用糖尿病数据集训练、评估模型(利用糖尿病数据集中的八个参数特征预测一个0或1结果)
- TF之NN之回归预测:利用NN算法(RelU)实现根据三个自变量预测一个因变量的回归问题
- ML之回归预测:利用八(9-1)种机器学习算法对无人驾驶汽车参数(2017年的data,18+2)进行回归预测+评估八种模型性能
- DL之DNN优化技术:神经网络算法简介之GD/SGD算法的简介、代码实现、代码调参之详细攻略
- 机器学习(三十三):Apriori 算法进行关联规则挖掘(实战)
- 基于鸽群算法优化的lssvm回归预测-附代码
- 智能优化算法:人工水母搜索算法 -附代码
- 数据结构和算法设计专题之---八大内部排序
- 【youcans 的 OpenCV 例程200篇】124. 孔洞填充的泛洪算法
- 利用python实现Apriori关联规则算法
- 算法笔记的学习心得和知识总结(四)|CodeUp and Pat篇(算法笔记第四章 哈希算法)