基于遺傳算法的不同形狀物體布局求解方法研究.pdf

1、布局求解是尋找多個(gè)較小物體在給定的約束條件下合理地放入特定的較大空間中，得到良好的擺放方案。布局問題屬于空間優(yōu)化問題，理論上屬于NP完全問題。由于涉及到物體及剩余空間形態(tài)的描述，直接利用數(shù)學(xué)中的優(yōu)化方法解決比較困難，而且物體布局由于自身形狀的復(fù)雜性，很難求得精確解。因此，布局問題研究的重點(diǎn)在于如何盡快找到該問題滿意解。合理的布局可以提高布局空間的利用率，降低運(yùn)輸、管理成本，提高企業(yè)的利潤有著極其重要的理論和現(xiàn)實(shí)意義。本文工作的重點(diǎn)是對不

2、同形狀物體布局求解方法進(jìn)行研究，該方法對物流運(yùn)輸?shù)呢浳镅b載以及生產(chǎn)工作車間部件的存放等空間資源的優(yōu)化利用等問題有著重要的指導(dǎo)意義。 本文首先對布局問題的國內(nèi)外研究現(xiàn)狀與研究方法進(jìn)行了綜述與分析，以及遺傳算法的實(shí)現(xiàn)技術(shù)進(jìn)行了分析。在此基礎(chǔ)上．重點(diǎn)研究了利用遺傳算法對不同形狀物體的布局方法進(jìn)行求解。通過Java語言開發(fā)一仿真系統(tǒng)，對于給定的不同形狀物體的布局進(jìn)行求解和計(jì)算機(jī)仿真，最后對系統(tǒng)運(yùn)行的結(jié)果進(jìn)行分析，結(jié)果表明，本文提出的方法

3、是有效的、正確的，而且具有較高的求解精度。 遺傳算法是基于自然選擇和基因遺傳原理進(jìn)行優(yōu)化求解。本文敘述了遺傳算法的理論基礎(chǔ)，性能分析和實(shí)現(xiàn)技術(shù)以及遺傳算法的約束條件。對不同形狀物體的布局求解采用了多參數(shù)符號(hào)混合編碼方法，同時(shí)提出了在選擇中采用了子-父代混合排序選擇策略，在遺傳過程中群體中的最優(yōu)個(gè)體總是遺傳到下一代中，這樣保證了算法能收斂于最優(yōu)解。在交叉和變異算子運(yùn)算中，保持了群體的多樣性，這樣求解過程克服了早熟現(xiàn)象的發(fā)生。通過實(shí)