遺傳算法和神經(jīng)網(wǎng)絡(luò)在布局子問(wèn)題中的應(yīng)用.pdf

1、遺傳算法是一類借鑒生物界自然選擇和遺傳機(jī)制的自適應(yīng)全局優(yōu)化隨機(jī)搜索算法.遺傳算法直接對(duì)結(jié)構(gòu)對(duì)象進(jìn)行操作,不存在函數(shù)可微性和連續(xù)性的限定,具有全局性,魯棒性和隱并行性等優(yōu)越性.神經(jīng)網(wǎng)絡(luò)是對(duì)人腦的信息處理方式進(jìn)行模擬的產(chǎn)物.1982年,Hofield提出離散神經(jīng)網(wǎng)絡(luò)模型并將其成功應(yīng)用于組合優(yōu)化問(wèn)題.至今應(yīng)用最為廣泛的神經(jīng)網(wǎng)絡(luò)BP網(wǎng)絡(luò)不僅具有強(qiáng)大的非線性映射能力,可以實(shí)現(xiàn)非常復(fù)雜的因果關(guān)系,而且具有自適應(yīng)、自學(xué)習(xí)和高容錯(cuò)性等優(yōu)良特性.布局問(wèn)題

2、是運(yùn)籌學(xué)的一個(gè)重要分支,屬于復(fù)雜的組合優(yōu)化問(wèn)題.20世紀(jì)70年代以來(lái)的研究表明,求解NPC問(wèn)題不存在既完整嚴(yán)格又不太慢的求解算法.因此遺傳算法和神經(jīng)網(wǎng)絡(luò)便理所當(dāng)然地成了解決組合優(yōu)化問(wèn)題并在速度和精度之間尋求平衡的工具.但將二者結(jié)合用于布局問(wèn)題的研究還很少見(jiàn)到,這方面課題有待進(jìn)一步研究,也具有一定的現(xiàn)實(shí)意義.本文主要內(nèi)容如下:1.構(gòu)造了同構(gòu)不干涉布局化算法.給出一個(gè)已知不干涉布局方案,該算法可以保證產(chǎn)生的布局方案與已知布局方案同構(gòu).2.回

3、顧遺傳算法的理論和應(yīng)用研究方面的進(jìn)展,定義了新的變異算子.給出了保持圖元鄰接關(guān)系的方法,構(gòu)造了同構(gòu)布局等價(jià)類的改進(jìn)遺傳算法.該算法不但能保證圖元的鄰接關(guān)系不變,并且能以較快的收斂速度搜索到全局最優(yōu)布局方案.3.將神經(jīng)網(wǎng)絡(luò)應(yīng)用到布局問(wèn)題中,給出了和局問(wèn)題的前向網(wǎng)絡(luò).結(jié)合遺傳算法,構(gòu)造了布局子問(wèn)題的遺傳神經(jīng)網(wǎng)絡(luò)算法.給出一組合理的訓(xùn)練樣本,該算法能較快地訓(xùn)練出適合的權(quán)值和閾值,并且能穩(wěn)定地收斂到較優(yōu)的布局方案.數(shù)值試驗(yàn)表明該算法是有效可行.