الگوريتم ژنتيك با جستجوي محلي براي حل مساله برنامه ريزي خطي صحيح

A Genetic Algorithm with Neighborhood Search to Solve Integer and Linear Programming Problems

دراين تحقيق، يك الگوريتم فراابتكاري از تركيب الگوريتم ژنتيك وجستجوي محلي، جهت حل مساله برنامه ريزي خطي صحيح ارايه مي گردد.جمعيت مورد بررسي بصورت باينري در يك دنباله از كروموزوم ها(متغيرها)كدگذاري مي شود.ابتدا طول كروموزوم ها ۵ بيت(ژن) انتخاب شدو درصورت لزوم براي يافتن جواب بهينه تا ۲۱ بيت قابل افزايش است.الگوريتم داراي يگ گام تست جهت بررسي رسيدن به جواب بهينه وتوقف يا ادامه جستجو مي باشد.دراين مقاله ما به مقايسه سه الگوريتم LINGO, Evolutionary, Simplex LP خواهيم پرداخت. نتايج نشان مي دهد كه الگوريتم ژنتيك نتايجي مشابه با الگوريتم هاي LINGOو SimplexLP امابهتر از Evolutionary مي باشد. مساله با دو، سه، چهار، هشت ودوازده متفير حل شده است.

In this research, a meta-heuristic algorithm is proposed to combine the genetic algorithm and the local search algorithm to solve the linear programming problem. The population under investigation is coded in binary in a sequence of chromosomes (variables). Initially, the length of the chromosomes is 5 bits (genes The algorithm is a test step to find the optimal solution and stop or continue the search. In this paper, we will compare three algorithms LINGO, Evolutionary, Simplex LP. The results show that the genetic algorithm has similar results to the LINGO and SimplexLP algorithms, but rather to Evolutionary. The problem is solved with two, three, four, eight, and twelve variables.