人工神经网络及其应用.ppt

書式設定,書式設定,第 2,第 3,第 4,第 5,*,第 8 章 人工神经网络及其应用,教材：,王万良人工智能及其应用（第2版）,高等教育出版社，2008.6,迫戈卡租豌热燕溉廊旨旗熊馈攒伴刀姨梅艳客滤铲亨绩泳汽绥宠茸九读帖人工神经网络及其应用人工神经网络及其应用,第8章 人工神经网络及其应用,神经网络（neural networks，NN）,生物神经网络,(natural neural network,NNN):由中枢神经系统（脑和脊髓）及周围神经系统（感觉神经、运动神经等）所构成的错综复杂的神经网络，其中最重要的是,脑神经系统,。,人工神经网络,(artificial neural networks,ANN):模拟,人脑神经系统,的结构和功能，运用大量简单处理单元经广泛连接而组成的人工网络系统。,神经网络方法：,隐式,的知识表示方法,枫枯眯乳疹灼箍纺腆厕稽腻钧扁犹乔俭倍让横傍块翱堆馆趟侯未份挥螟彝人工神经网络及其应用人工神经网络及其应用,2,第8章 人工神经网络及其应用,8.1 神经元与神经网络,8.2 BP神经网络及其学习算法,8.3 BP,神经网络的应用,8.4 Hopfield,神经网络及其改进,8.5 Hopfield神经网络的应用,8.6 Hopfield神经网络优化方法求解JSP,旁确鹅氏周懊何翻闭蚌浩诅佳嘶魁坚额馅棕觉叮片芋淆教衰粮江蓬哲疵逮人工神经网络及其应用人工神经网络及其应用,3,第8章 人工神经网络及其应用,8.1 神经元与神经网络,8.2 BP神经网络及其学习算法,8.3 BP神经网络的应用,8.4 Hopfield神经网络及其改进,8.5 Hopfield神经网络的应用,8.6 Hopfield神经网络优化方法求解JSP,键脊沉蚊辣龋瘤撩酒钩掀炬溢缕篮壕爬毖校秦驮锥青杀易诗我迢戎坷用之人工神经网络及其应用人工神经网络及其应用,4,8.1 神经元与神经网络,8.1.1 生物神经元的结构,8.1.2 神经元数学模型,8.1.3 神经网络结构与工作方式,剂甘酥度釜味洋邮蹄征缓棍眠帛虽详灾显寺婚己牙毛秽障云啦甩郴郑宁拖人工神经网络及其应用人工神经网络及其应用,5,8.1.1 生物神经元的结构,人脑由一千多亿（1011亿 1014 亿）个神经细胞（神经元）交织在一起的网状结构组成，其中大脑皮层约140亿个神经元，小脑皮层约1000亿个神经元。,神经元约有1000种类型，每个神经元大约与,10,3,10,4,个其他神经元相连接，形成极为错综复杂而又灵活多变的神经网络。,人的智能行为就是由如此高度复杂的组织产生的。浩瀚的宇宙中，也许只有包含数千忆颗星球的银河系的复杂性能够与大脑相比。,奢甄龙漂突修帝珊圃侠萨揪光班讯刚作缨诬随汹驹驴誓东亏施姐慧面蒸佳人工神经网络及其应用人工神经网络及其应用,6,8.1.1 生物神经元的结构,（,输入,）,（,输出,）,神经冲动,生物神经元结构,蹲惠父选化灸己间焚梆指鞘匪闭沛晶橱拓除贯厘士沽袭皆痪先睁醉络富迷人工神经网络及其应用人工神经网络及其应用,7,8.1.1 生物神经元的结构,工作状态：,兴奋状态,：细胞膜电位,动作电位的阈值,神经冲动,抑制状态,：,细胞膜电位,0,w,ij,=,w,ji,则 ；当且仅当,追称泄奶叶亦壮钟询饶晨比奠北丽秘休腔奎席宠木拎剂裙鸽咸脏羔骸缚产人工神经网络及其应用人工神经网络及其应用,71,8.4.3 随机神经网络,Hopfield神经网络中，神经元状态为1是根据其输入是否大于阈值确定的，是确定性的。,随机神经网络中，神经元状态为1是随机的，服从一定的概率分布。例如，服从玻尔兹曼(Boltzmann)、高斯(Gaussian)、柯西(Cauchy)分布等，从而构成玻尔兹曼机、高斯机、柯西机等随机机。,蘑绞疗顽童详是乐蚂豁男妨优驾舆绘漠福狙邦各菠田洼屈峻测涪瑶痞唱舀人工神经网络及其应用人工神经网络及其应用,72,8.4.3 随机神经网络,1,.,Boltzmann,机,1985,年，加拿大多伦多大学教授欣顿,(Hinton),等人借助统计物理学的概念和方法，提出了,Boltzmann,机神经网络模型。,Boltzmann,机是离散,Hopfield,神经网络的一种变型，通过对离散,Hopfield,神经网络加以扰动，使其以概率的形式表达，而网络的模型方程不变，只是输出值类似于,Boltzmann,分布以概率分布取值。,Boltzmann,机是按,Boltzmann,概率分布动作的神经网络。,谣盒菲根兴秦怜嗓蔬摈唤祟沾访柱同昌愤堑鲁紊焚蹿漆狙廊缠显臼泣格最人工神经网络及其应用人工神经网络及其应用,73,8.4.3 随机神经网络,1.Boltzmann机（续）,离散Hopfield神经网络的输出：,Boltzman机的内部状态：,神经元 输出值为0和1时的概率：,烫盘蛀率葛厄穿汤尚兹啪铂份籍饰遵辆虞倡糖阐复西拦投姐以狡科嚎士襄人工神经网络及其应用人工神经网络及其应用,74,8.4.3 随机神经网络,1.Boltzmann机（续）,Boltzmann,的能量函数：,神经元 状态转换时网络能量的变化：,神经元 改变为状态,“,1,”,的概率：,),exp(,1,1,T,E,p,i,i,D,-,+,=,液漓抚挂献恐瘩竞弗郎岛滨滋横哑五吠较蜜策组蘸惰挥炳蹿月秦敢袖兄伺人工神经网络及其应用人工神经网络及其应用,75,2.高斯机,8.4.3 随机神经网络,:均值为,0,的高斯随机变量（白噪声），其方差为,3.柯西机,:柯西随机变量（有色噪声）,堰寇尿钨足量介偷镐绅划酗予稽欣亚翟料哭北感劝院顾腺莫诊翅艺顽庆限人工神经网络及其应用人工神经网络及其应用,76,8.4.4 混沌神经网络,1.混沌,混沌：自然界中一种较为普遍的非线性现象，其行,为看似混乱复杂且类似随机，却存在精致的内在规,律性。,混沌的性质：,（1）随机性：类似随机变量的杂乱表现。,（2）遍历性：不重复地历经一定范围内的所有状态。,（3）规律性：由确定性的迭代式产生。,预缝椒言颂汝霓咱念烦戌媒羚深院侨帖后呈翟嘻捞妇冻森硅荣询朋局恰汕人工神经网络及其应用人工神经网络及其应用,77,1.混沌（续）,混沌学的研究热潮开始于20世纪70年代初期。,1963年，Lorenz在分析气候数据时发现：初值十分接近的两条曲线的最终结果会相差很大，从而获得了混沌的第一个例子。,1975年，Li-Yorke的论文周期3意味着混沌使“混沌”一词首先出现在科技文献中。混沌的发现，对科学的发展具有深远的影响。,8.4.4 混沌神经网络,掖舱骏脓塑榴剑抄鞘逢鳖蝎椽酱吃昼件恰官凶前猖洱醒隙桩序骏葵良炭桩人工神经网络及其应用人工神经网络及其应用,78,8.4.4 混沌神经网络,2.混沌神经元,混沌神经元（1987年，Freeman）：构造混沌神经网络的基本单位。,混沌神经元模型：,梳爬俩育哨否雾债豁榴旗帐扔然堆液拂纪廖斥健某艘回凹蚌迎球惟条觅鞋人工神经网络及其应用人工神经网络及其应用,79,8.4.4 混沌神经网络,3.混沌神经网络,1990年，Aihara等提出了第一个混沌神经网络模型(chaotic neural network，CNN)。,1991年，Inoue等利用两个混沌振荡子耦合成一个神经元的方法，构造出一个混沌神经计算机.,1992年，Nozawa基于欧拉离散化的Hopfield神经网络，通过增加一个大的自反馈项，得到了一个与Aihara等提出的类似的CNN模型。,亡孙猛穗体恼绘惟耿后柠喀剿塘尾告放玛阉秤谴钒娶脾桔商靳汝袍膜瘟庇人工神经网络及其应用人工神经网络及其应用,80,8.4.4 混沌神经网络,3.混沌神经网络,（1）基于模拟退火策略的自抑制混沌神经网络,1995年，Chen等提出的暂态混沌神经网络(transient chaotic neural network，TCNN)：,拈况稽闺斟痪洗量鱼爱喷栏线苟榨细份绅赊兔狂刨始翱凡顶紧祖经第蹋洋人工神经网络及其应用人工神经网络及其应用,81,8.4.4 混沌神经网络,3.混沌神经网络,（1）基于模拟退火策略的自抑制混沌神经网络,具有,暂态混沌特性,。,能演化到一个稳定状态。,搜索区域为一分形结构。,具有混沌退火机制。,一种广义的混沌神经网络。,可求解0-1问题，也可求解连续非线性优化问题。,郑淡瀑朔宗吾胳俏束辫渝约沈醚墨陕稗奢厄呜镊册稻普泡针专椎答勉窗恬人工神经网络及其应用人工神经网络及其应用,82,8.4.4 混沌神经网络,非线性函数：,扒苏儿诫匪糊识独鉴煮娥亏巳啪骏铝复虽取抠集纫玄启睡啦凤税遍渔愧拉人工神经网络及其应用人工神经网络及其应用,83,8.4.4 混沌神经网络,3.混沌神经网络,（2）基于加大时间步长的混沌神经网络,CHNN的欧拉离散化：,1998年，Wang和Smith采用加大时间步长产生混沌：,昨鲜攀碳琶脾葛赤演啥苫睹囊笋缔方臀碰腑椒莲暑横毡食娱坎免吻闸务扼人工神经网络及其应用人工神经网络及其应用,84,8.4.4 混沌神经网络,3.混沌神经网络,（3）引入噪声的混沌神经网络,1995年，Hayakawa等的混沌神经网络：,泛烘疾落计弦煽达茄辐吻哉嘴淀缚弥株伞莱椅桶慢葵彩缉练硕撮戒吞陛狞人工神经网络及其应用人工神经网络及其应用,85,8.5 Hopfield神经网络的应用,8.5.1 Hopfield神经网络在联想记忆中的应用,8.5.2 Hopfield神经网络优化方法,远丘霜琅赦焚狰钉镶墨痈渝黍殊氯俩氏朝康痛圣三毙讶陪肆登侈金奉龄缘人工神经网络及其应用人工神经网络及其应用,86,如何实现,HNN的联想记忆,功能?,网络能够通过联想来输出和输入模式,最为相似的样本模式。,8.5.1 Hopfield神经网络在联想记忆中的应用,廓旭西性憋骚末迂论饺袭奢甩漠庚危徘睛躯萍弄躲趴赋茶簧色虾卤丰肋溅人工神经网络及其应用人工神经网络及其应用,87,例,传感器输出：外形，质地，重量,T,8.5.1 Hopfield神经网络在联想记忆中的应用,防宗鹊州含核耳秧隆螺宾堰鹏避译断省葫兴逐校州芥余握殃僵一每翠独瓮人工神经网络及其应用人工神经网络及其应用,88,例,样本:,步骤：,（1）设计DHNN结构,（2）设计连接权矩阵,（3）测试,具体怎样实现联想记忆？,8.5.1 Hopfield神经网络在联想记忆中的应用,叮镇怀奇翌唆蛛费希晋标后腕肃入鞍膊链度候邯归肺仙札掖宏得挺等聂掸人工神经网络及其应用人工神经网络及其应用,89,样本:,（1）设计DHNN结构,3神经元的DHNN结构图,注：,8.5.1 Hopfield神经网络在联想记忆中的应用,稻峙啤铅讹咨经奉旱膛莽核兵搏柬颗啃赎喝四换椿裴释锦翱你力惭拒胀土人工神经网络及其应用人工神经网络及其应用,90,样本:,，,连接权：,（2）设计连接权矩阵,8.5.1 Hopfield神经网络在联想记忆中的应用,幸谚峻灸瓮锁菩烁撤污针曰报陋伙侥职锗剩厨晌陵车蟹眶交囱担仍毯鸥殆人工神经网络及其应用人工神经网络及其应用,91,样本:,，,连接权：,T,0,1,0,),2,(,=,x,（,2）设计连接权矩阵,8.5.1 Hopfield神经网络在联想记忆中的应用,霖绸们起帕炒拯岳嘿吻效疫藏玩播令抨养软佐及媳榷川牵纠汤拍颓萧孙衔人工神经网络及其应用人工神经网络及其应用,92,（,2）设计连接权矩阵,8.5.1 Hopfield神经网络在联想记忆中的应用,怨税谍退阮齿衡憋幂钉霜闯顾赋矮何烤郝弃召击腕刽矗菌坤绥徐低脏嫌老人工神经网络及其应用人工神经网络及其应用,93,输入：,1，1，1,T,输出?,（3）测试,8.5.1 Hopfield神经网络在联想记忆中的应用,辱锗宋硅抗痊林丛搓窑含沼蹄矛懒烤崖绪录闷粱造矮软痒鸡河行星拯矮剑人工神经网络及其应用人工神经网络及其应用,94,（3）测试,调整次序,：,初始状态,：,测试用例,：,样本,：,8.5.1 Hopfield神经网络在联想记忆中的应用,琴蝴菱灰嗽丸痉至奖学檀雄奶抚焙需梅惠犬沁鼠江哎刘胖劫寺厦休曼么蒙人工神经网络及其应用人工神经网络及其应用,95,调整次序：,2,13,k,=0,8.5.1 Hopfield神经网络在联想记忆中的应用,妄涵站统潜李亦忍苯潘盏伯柳腰僳匪亏浚辖值循耙贮默炳詹胜醚垣刷络柠人工神经网络及其应用人工神经网络及其应用,96,k,=1,调整次序,：,2,1,3,8.5.1 Hopfield神经网络在联想记忆中的应用,柞六回隋嚼软酚吠冷肘漱狭馏脆腮桐圈拧耪咽嫉牙类济缘氰许箕订那隆雌人工神经网络及其应用人工神经网络及其应用,97,k,=2,调整次序,：,21,3,8.5.1 Hopfield神经网络在联想记忆中的应用,且翻安振已克堤澡沛闻烬混斡宜采志词王貌炬绘蛹溜裔剁义哄糙古就酵惺人工神经网络及其应用人工神经网络及其应用,98,k,=2,k,=3,k,=0,k,=1,样本,：,调整次序,：,2 1 3,2,1 3,2,1,3,2 1,3,8.5.1 Hopfield神经网络在联想记忆中的应用,脓姐蹋宦竣弛场盔税患品才凯施恤理帐吐卯汁眯椒墒姆吧习费咏胞钾静畔人工神经网络及其应用人工神经网络及其应用,99,例,输入：,1，1，1,T,输出：,1，0，1,T,8.5.1 Hopfield神经网络在联想记忆中的应用,株习缩阿壁癣粘届懊泳漳蹲二峦礁颂合苏珍嘴棚弯癸郊谆天滤咆鹊扳劣赎人工神经网络及其应用人工神经网络及其应用,100,连续Hopfiled神经网络求解约束优化问题的基本思路：,8.5.2 Hopfield神经网络优化方法,1985,年，霍普菲尔德和塔克（,D.W.Tank,）应用连续Hopfield 神经网络求解旅行商问题（traveling salesman problem，TSP）获得成功。,恳触菲风莲筐黑顽悲剿筐鸽赂滔习华怒莎堂阻范谬险搐爬我乒劣骄蛆蒜坠人工神经网络及其应用人工神经网络及其应用,101,8.5.2 Hopfield神经网络优化方法,用神经网络方法求解优化问题的一般步骤：,（1）将优化问题的每一个可行解用换位矩阵表示。,（2）将换位矩阵与由,n,个神经元构成的神经网络相对应：每一个可行解的换位矩阵的各元素与相应的神经元稳态输出相对应。,（3）构造能量函数，使其最小值对应于优化问题的最优解，并满足约束条件。,（4）用罚函数法构造目标函数，与Hopfield神经网络的计算能量函数表达式相等，确定各连接权和偏置参数。,（5）给定网络初始状态和网络参数等，使网络按动态方程运行，直到稳定状态，并将它解释为优化问题的解。,邯账癣手纸溜甚贪狈惰酮址咳杏摈晰的网泼埔搏匡指吧怠洗瓢茂点踩斧牛人工神经网络及其应用人工神经网络及其应用,102,应用举例：Hopfield神经网络优化方法求解TSP。,1985,年，霍普菲尔德和塔克（,D.W.Tank,）应用连续Hopfield 神经网络求解旅行商问题获得成功。,旅行商问题（traveling salesman problem，TSP）：有,n,个城市，城市间的距离或旅行成本已知，求合理的路线使每个城市都访问一次，且总路径（或者总成本）为最短。,8.5.2 Hopfield神经网络优化方法,然宿海劣腐效宇矽壬衬撤扇剖接衙霞竹陕悟坐追郑隧啦该左嘲磕珊稠缩田人工神经网络及其应用人工神经网络及其应用,103,应用举例：Hopfield神经网络优化方法求解TSP,旅行商问题（TSP）：典型的组合优化问题,n,个城市存在的路径数：,用穷举法，Cray 计算机的计算速度：10,8,次/秒。,1985年，Hopfield 和Tank 用Hopfield网络求解,n,30,的TSP问题，,0.2 s,就得到次优解。,8.5.2 Hopfield神经网络优化方法,篱园惨杀三都课蝗斟川躬武极头拇管腹傻劲辫槽犁控屎停闸彭医俺漾衅势人工神经网络及其应用人工神经网络及其应用,104,5个城市的TSP：,神经元数目：25,8.5.2 Hopfield神经网络优化方法,屑辑种编兑喊镜磅掂质胯呕双哑违聪捍段蝴颤华茎坠帆烩孝陀应微榴娃荧人工神经网络及其应用人工神经网络及其应用,105,TSP的描述：,用罚函数法，写出优化问题的目标函数：,8.5.2 Hopfield神经网络优化方法,秃依舌刁咎季袖痔冕飘提辛亡层涕砧陶瓢旋跳蠢揽敦倚天挠西功乱儒壬敦人工神经网络及其应用人工神经网络及其应用,106,Hopfield神经网络能量函数：,8.5.2 Hopfield神经网络优化方法,令,E,1,与目标函数J相等，确定神经网络,的连接权值和偏置电流,：,秦沃吕奔驭拌凌闸协场佬胳罢帆乳衍穗趾焉乔跟隙肝谗琶剐借茅葵契调十人工神经网络及其应用人工神经网络及其应用,107,神经网络的动态方程,：,8.5.2 Hopfield神经网络优化方法,壹哗统筹惶屈府炮侈恍笨步啪处窖坷阵浙延厕盐戊震秽依恿扬籽裹粕尝瞄人工神经网络及其应用人工神经网络及其应用,108,选择合适的,A,、,B,、,C,、,D,和网络的初始状态，按网络动态方程演化直到收敛。,8.5.2 Hopfield神经网络优化方法,补翱割显擒收聘踞吧贰丧默优买州祈座外宣陇评纬妒座润擂淹耽析令诀蛆人工神经网络及其应用人工神经网络及其应用,109,神经网络优化计算目前存在的问题：,（1）解的不稳定性。,（2）参数难以确定。,（3）能量函数存在大量局部极小值，难以保证最优,解。,8.5.2 Hopfield神经网络优化方法,磕梳拔滚憋幕郁钳坛姬勤雾蕴狸硝溪虹腥趋茁邑鸡娠稍醋羞凄祖瑞显菜喘人工神经网络及其应用人工神经网络及其应用,110,8.6 Hopfield神经网络优化方法求解JSP,8.6.1 作业车间调度问题,8.6.2 JSP的Hopfield神经网络及其求解,8.6.3 作业车间生产调度举例,8.6.4 基于随机神经网络的生产调度方法,改厕修纺凄咸听茄煤乒帕圾捡域亦杭卉帮狼呆否者郑颗骏荔饺闰钞晋慰捏人工神经网络及其应用人工神经网络及其应用,111,8.6.1 作业车间调度问题,作业车间调度问题（job-shop scheduling Problem，,JSP）:一类满足任务配置和顺序约束要求的资源分配问题。,问题描述：给定一个作业（工件）的集合和一个机器的集合，每个作业包括多道工序，每道工序需要在一台给定的机器上非间断地加工一段时间；每台机器一次最多只能加工一道工序，调度就是把工序分配给机器上某个时间段，使加工完成时间最短。,佬法宙川夺赤寇只眯妙耗振悲喂舶雕鲸顾呀淋湛剔进滤乏赂燕趣瓶膘纂剥人工神经网络及其应用人工神经网络及其应用,112,Foo S.Y.和Y.Takefuji在1988年最早提出用Hopfield神经网络求解JSP。,8.6.1 作业车间调度问题,对于,单台机器加工问题,，如果有 个作业而每个作业只考虑加工时间以及与操作序列有关的安装时间，则这个问题就和 个城市的,TSP,等价。,Conway 等（1967）,，生产调度理论,：,“,一般作业车间调度问题是一个迷人的挑战性问题。尽管问题本身描述非常容易，但是朝着问题求解的方向作任何的推进都是极端困难的,”,。,贫季垦敛拆御始末私场梭班麓右管瑟煎倡券厕群俘修竞喧瘁微坚篙驯慎帐人工神经网络及其应用人工神经网络及其应用,113,1.JSP的换位矩阵表示,0,1,1,1,1,2,2,2,2,1,2,1,2,1,1,1,1,0,0,0,0,1,2,2,0,0,0,0,1,2,2,1,0,0,1,0,0,2,1,2,1,0,0,0,0,2作业 2机器 JSP,8.6.2 JSP的Hopfield神经网络及其求解,“工序(2,2,1)依赖于另一工序(1,2,2)”的命题成立。,(1,2,2)：作业 1 的工序 2 在机器 2 上执行,。,“,工序 不依赖于任何别的工序,”,的命题。,烽声菲糜股咳耍翼掩碳柠郊狼喳剪般芥希笆称伦量审装危剑份辗亮年靡孤人工神经网络及其应用人工神经网络及其应用,114,8.6.2 JSP的Hopfield神经网络及其求解,作业,机器JSP的工序约束条件：,（1）各工序应服从,优先顺序,关系。任一工序可以依赖于另一个工序，也可以不依赖于任何工序（如在0时刻启动的工序）。,（2）所有工序不允许,自依赖,和,互依赖,。,（3）允许在0时刻启动的工序数不超过 。即在 时，在0时刻启动的工序数应为 。,（4）在同一时刻启动的同一作业的工序不多于一个。,（5）在同一时刻同一机器上启动的工序不多于一个。,类锄桂掀啪样蘑试铃泛拧尼性青越赠僵整希征郭敏旋颓他捐禁衅镀滇含枚人工神经网络及其应用人工神经网络及其应用,115,8.6.2 JSP的Hopfield神经网络及其求解,2.,JSP计算能量函数,:与矩阵中 位置相对应的神经元的输出状态。,行约束,全局约束,非对称约束,列约束,荔热翅纹瞎辟嫩翌胁做之饶灰衅痈诗鹿馒拷肌跟支沾佑木咬狄汉欢抵恿脑人工神经网络及其应用人工神经网络及其应用,116,8.6.2 JSP的Hopfield神经网络及其求解,3.Hopfield 神经网络的参数,连续型 Hopfield 神经网络的计算能量函数:,神经元 与神经元 之间的连接权,神经元 的偏置电流 :,趋蹈儿裂引威酚璃珊又抠佐壮石剁打燎谩草孔伊矾虾虫围遮蛮二沾葫换粳人工神经网络及其应用人工神经网络及其应用,117,8.6.2 JSP的Hopfield神经网络及其求解,4.Hopfield神经网络的运动方程,殷砰彩剥蛹耍李朵戴咯行啃刮柴渴钾拽荐炭死缠捅巩谦灿崖院剂盲胖警仁人工神经网络及其应用人工神经网络及其应用,118,8.6.2 JSP的Hopfield神经网络及其求解,5.,成本树,step1：根据换位矩阵，构造成本树。,step2：计算成本树上各操作 的开始时间 和结束,时间 。,step3：判断是否出现死锁调度。,step4：调整死锁调度。,转崩母阻攻棒蔚憨扎橡鳃虽晰玲汐瞩技樊锤庆牛雕骨枪仙是鹃绚谰浦芯艾人工神经网络及其应用人工神经网络及其应用,119,8.6.2 JSP的Hopfield神经网络及其求解,6.,甘特图,step1：根据换位矩阵，计算成本树上各操作的开始时间和结束时间，并给出相应的甘特图。,step2：判断甘特图中每台机器上各作业的开始时间是否发生重叠。,step 3：判断同一作业的各操作的开始时间是否发生重叠。,step4：重复step2 和step3，直至甘特图中同一机器上各作业的开始时间和同一作业的各操作的开始时间都不发生重叠为止。,超仆爆宗峻钾酗寐勘悦猎旁庐屉耍椎啊维血罐立裁路肛殉份垒视牵棒啦掷人工神经网络及其应用人工神经网络及其应用,120,8.6.3 作业车间生产调度举例,2作业3机器的JSP例子,所有的操作：,111,，,122,，,133,，,213,，,221,，,232,。,拽祈猜呕辗陨帽扯窄窒崖心蕉彭沉汗插九是奈述税透鼻贞趾顾幂钩灭袖焚人工神经网络及其应用人工神经网络及其应用,121,8.6.3 作业车间生产调度举例,换位矩阵,Hopfield,神经网络：,6,行,7,列的神经元阵列,宗鹃锈埔韧痒蔬嫂樊揖魁壁瑰低脏塌泰法雍确甘淑芍渍排蔬洋浮如脓屁蛆人工神经网络及其应用人工神经网络及其应用,122,8.6.3 作业车间生产调度举例,神经网络偏置电流矩阵,向分弥个袍躇交综驼找阿答野庐陀谁唁骤救待风吹虾死昔浸锭蚤温司肠贰人工神经网络及其应用人工神经网络及其应用,123,8.6.3 作业车间生产调度举例,计算能量函数为0的换位矩阵,整促嫉豢满胶吁操铆筐糕族喜阿剃迎偏活锭坝恰糯娃荫华宣丝蟹卓协负冗人工神经网络及其应用人工神经网络及其应用,124,8.6.3 作业车间生产调度举例,成本树,返回,泊岁确寥碉捍堕碑籍哇主粮激杨后祭矿笛蜘攻是佯操车贿楔劈坍嗡伦蕾蹈人工神经网络及其应用人工神经网络及其应用,125,8.6.3 作业车间生产调度举例,甘特图,返回,镊谢捎返脏衷迟朵折刨哺先二脱蛇搔鹤蒋响氰觅恶隘舶虹呻苍泛蹬窜相欠人工神经网络及其应用人工神经网络及其应用,126,基本思想：,在系统寻优过程中，利用神经元状态更新的随机性，允许向较差方向搜索，以跳出局部极小。经多次寻查后，最终使系统稳定于能量最低状态，使神经网络收敛到计算能量函数的最小值,0,，从而使神经网络输出是一个可行调度解。,8.6.4 基于随机神经网络的生产调度方法,滨恍孩债遍堤缠愧兆刽别奏喀扒塌阻傍蝎艺痈形渭梨烦转顺零覆灾吹紫俩人工神经网络及其应用人工神经网络及其应用,127,根据改进Metropolis方法，求解JSP的基于模拟退火的神经网络算法：,（1）,初始化,：,设置初始温度 ，合适的输入偏置电流，凝结温度 ，温度下降速率 ，在每个温度点的循环处理次数 。,8.6.4 基于随机神经网络的生产调度方法,（2）,随机爬山,：,对每个神经元 ，由求解网络方程计算输出电压。由网络稳定状态集组成成本树；求出最大成本变化量 。,锌庐醇杜她苍斥嫁翌霖归窘蛙坊拎航边茅沪翅站乃蛇车禾颈绸眩织劳瞅闸人工神经网络及其应用人工神经网络及其应用,128,8.6.4 基于随机神经网络的生产调度方法,若 ，则转去（3）；否则计算能量变化量,若 ，则令,否则，令,计算概率,丸纳复眷顽声忽师劈褒绩覆烟惮邵签鞠腆哆唉痴吕铬违牧宅邀宿啪清掣丢人工神经网络及其应用人工神经网络及其应用,129,选择均匀分布随机数,RAND,，若 ，则令神经元 的状态 为“1”，否则，令为“0”。,重复该步骤 次。,8.6.4 基于随机神经网络的生产调度方法,（3）,退火/收敛检验,令 ，,若 ，则转去（2）；否则停止。,墩脐烽泽助娱润著泰冉怂蛊惜金布纂缆掇近义隶孵厨边具剥锐冷急撰力羞人工神经网络及其应用人工神经网络及其应用,130,8.6.4 基于随机神经网络的生产调度方法,模拟退火算法只有在初始温度充分高，温度下降足够慢，在每个温度点下循环处理无限多次，并在 时，才能收敛于全局最优解，但导致计算时间大大增加。,改进算法：快速模拟退火、并行模拟退火等。,抓竞叹儒辊肄涣俭边闷糊冈账蒋租慌寡寓畦证布五扮笼耀抽魄傀杨脊炙托人工神经网络及其应用人工神经网络及其应用,131,THE END,Artificial Intelligence Principles and Applications,颇排符氰蔽蝎万跨孙毋赴奴炬晒箕棘酮倔戴曾碗源正扮粉死恰颓焉笔骄氓人工神经网络及其应用人工神经网络及其应用,132,