26082

الگوريتم‌ فراكاوشي شبيه‌سازي تبريد براي انتخاب پايه سيكل‌ شبه‌بهينه يك گراف

كارشناسي ارشد

مهندسي عمران - گرايش سازه

1398-1400

1400/11/24

دكتر علي كاوه

مهندسي عمران

پايه‌هاي سيكلي يك گراف در طيف گسترده اي از مسائل مهندسي به وجود مي‌آيند و كاربردهاي متنوعي دارند. پايه‌هاي سيكلي كمينه و بهينه، زمان و حافظه مورد نياز براي برخي كاربردها را كاهش مي‌دهد. يكي از مهم‌ترين كاربردهاي پايه‌هاي سيكلي بهينه در مهندسي عمران، استفاده از آن در روش نيروها براي پُر صفر (تُنُك) كردن ماتريس نرمي سازه مي‌باشد، كه براي تحليل بهينه سازه‌ها اهميت زيادي دارد. در اين تحقيق از الگوريتم‌ شبيه‌سازي تبريد و الگوريتم بهينه‌سازي كلوني مورچگان براي تشكيل پايه سيكل استفاده شده است. الگوريتم شبيه‌سازي تبريد با استفاده از جستجوي محلي و توليد پاسخ همسايه كار مي‌كند و همچنين با پذيرش جواب‌هاي بد از بهينه‌هاي محلي فرار مي‌كند، نتايج به‌دست آمده نشان مي‌دهد از اين الگوريتم مي‌توان براي توليد پايه‌هاي سيكلي شبه-بهينه و شبه-كمينه استفاده كرد و در مقايسه با الگوريتم‌هاي ابتكاري موجود نتايج بهتري را ارائه مي‌دهد و يكي از مزاياي اين الگوريتم ساده بودن آن است كه مي‌توان آن را به‌راحتي پياده‌سازي كرد. الگوريتم مورچگان نيز براي تشكيل پايه‌هاي سيكلي استفاده شده است اما نتايج ضعيف‌تري نسبت به الگوريتم شبيه‌سازي تبريد ارائه مي‌دهد و همچنين زمان اجراي آن طولاني‌تر است.

1400/11/27

Simulated Annealing metaheuristic algorithm for selecting suboptimal cycle basis of a graph

2/13/2023 12:00:00 AM

The cycle basis of a graph arises in a wide range of engineering problems and has a variety of applications. Minimal and optimal cycle bases reduce the time and memory required for most applications. One of the most important applications of optimal cycle basis in civil engineering is its use in the force method to sparse the flexibility matrix of a structure, which is very important for the optimal analysis of structures. In this research, the simulated annealing algorithm and the ant colony optimization algorithm have been used to form the cycle basis. The simulated annealing algorithm works by using local search and generating neighbor solution, and also escapes local optima by accepting worse solutions. The results show that this algorithm can be used to generate sub-optimal and sub-minimal cycle bases. Compared to existing heuristic algorithms, it gives better results and one of the advantages of this algorithm is its simplicity that it can be easily implemented. The ant colony algorithm has also been used to form cycle bases, but for the studied examples, it offers poorer results than the simulated annealing algorithm and also has a longer execution time.

پايه سيكل شبه بهينه , تئوري گراف , الگوريتم‌هاي فراكاوشي , روش نيروها , تحليل بهينه سازه‌ها

Suboptimal Cycle Basis , Graph Theory , Metaheuristic Algorithms , Force Method , Optimal Structural Analysis