求解等圓Packing問題的遺傳擬物混合算法.pdf

1、等圓Packing問題是一類非常典型的NP-Hard問題。它屬于Packing問題的一種。此類問題在玻璃、鋼板、木材、紙張和制衣等工程應(yīng)用領(lǐng)域中具有非常高的應(yīng)用價(jià)值。由于NP-Hard問題的復(fù)雜性，不能用常規(guī)的解法，比如幾何方法求解。因此必須提出非常有效的啟發(fā)式方法來近似地求解。
　　 擬物方法作為一種非常有建設(shè)性的方法，它通過觀察和模擬物理世界中的物體運(yùn)動(dòng)規(guī)律，來設(shè)計(jì)求解模型。通過將數(shù)學(xué)問題轉(zhuǎn)換為物理模型進(jìn)行計(jì)算，最終得到問題

2、的解。本等圓Packing問題所模擬的物理模型為彈性球模型。通過將每個(gè)小圓設(shè)想為彈性實(shí)心小圓，把大圓設(shè)想為中空剛體，根據(jù)受力運(yùn)動(dòng)的模擬得到最終相對(duì)穩(wěn)定位置作為問題的解。
　　 在實(shí)際的對(duì)物理過程進(jìn)行模擬的動(dòng)態(tài)過程中，一般使用逐步小量移動(dòng)的迭代方法。此方法在模擬物理過程上，存在一定數(shù)學(xué)上的精確性問題。通過改進(jìn)原有擬物算法，使每次小量移動(dòng)的大小根據(jù)情況而可以改變大小，以使得總勢(shì)能嚴(yán)格單調(diào)遞減。此改進(jìn)可以取得更好的收斂效果。