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

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

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