حل مسئله ۸ وزیر با الگوریتم SA در پایتون

در این بخش حل مسئله ۸ وزیر با الگوریتم SA در پایتون قرار داده شده است. مسائل بهینه سازی مختلفی وجود دارند که می‌توانند به روش‌های مختلفی حل شوند. یکی از بهترین گزینه‌های موجود، استفاده از الگوریتم های فرا ابتکاری است که با استفاده از آن می‌توان مسئله‌ای مانند ۸ وزیر یا  وزیر را حل نمود. از جمله الگوریتم های فرا ابتکاری که قدرت بالایی در این زمینه دارد، می‌توان به الگوریتم SA یا الگوریتم تبرید شبیه سازی شده اشاره کرد.

یکی از رده بندی‌های NP_Complet در حوزه مسئله‌های بهینه سازی ترکیباتی مسئله ۸ وزیر می‌باشد و الگوریتم تبرید شبیه سازی شده simulated annealing در هوش مصنوعی در این زمینه می‌تواند مورد استفاده قرار گیرد. در این سورس کد علاوه بر مسئله ۸ وزیر حل مسئله n وزیر با با الگوریتم SA در پایتون (چند وزیر) در اختیار شما قرار می‌گیرد.

الگوریتم شبیه سازی تبرید SA

الگوریتم شبیه سازی تبرید یا تبرید شبیه سازی شده Simulated Annealing که در بسیاری موارد با نام الگوریتم شبیه سازی حرارتی نیز شناخته می‌شود، از جمله الگوریتم های متاهیورستیک یا فرا ابتکاری است که برای حل مسائل بهینه سازی مورد استفاده قرار می‌گیرد. یکی از مسائلی که برای حل آن می‌توان از الگوریتم شبیه سازی تبرید SA استفاده کرد، مسئله n وزیر می‌باشد.

الگوریتم شبیه سازی حرارتی SA با الهام از روش باز پخت فلز به وجود آمده است. روش باز پخت، آرایش مولکولی بهینه ذرات فلز را که در آن انرژی پتانسیل جرم به حداقل می‌رسد، را تعریف می‌کند و به خنک شدن تدریجی فلزات پس از قرار گرفتن در معرض حرارت زیاد اشاره می‌کند. به‌طور کلی، الگوریتم شبیه سازی حرارتی SA یک حرکت تکراری را با توجه به پارامتری به نام دما که متغیر است، انجام می‌دهد که برای انجام آن، از عملیات انجام‌شده در کار باز پخت فلزات تقلید می‌کند.

مسئله هشت وزیر

مسئله هشت وزیر از جمله مسائل کلاسیک در مباحث طراحی الگوریتم است که در حالت کلی‌تر با عنوان معمای n وزیر یا معمای چند وزیر مطرح می‌شود. وزیر یا Queen (که در بازی‌های بین المللی اصطلاحی هم نام با معنی اش یعنی ملکه دارد ولی در کشور ما از اصطلاح وزیر استفاده می‌شود) مهره‌ای از مهره‌های بازی شطرنج است که می‌تواند در تمامی هشت جهت به هر تعداد خانه (تا زمانی که مهره‌ای مانع نباشد) حرکت کند. اگر در این مسیرها مهره‌ای از حریف قرار گرفته باشد، آن مهره در معرض خطر حمله توسط وزیر قرار دارد یا به اصطلاح وزیر آن مهره را تهدید می‌کند.

هدف از معمای هشت وزیر، قرار دادن ۸ مهره‌ی وزیر روی یک صفحه‌ی شطرنج خالی است، به قسمتی که هیچ مهره‌ای (وزیری)، مهره‌های (وزیرهای) دیگر را تهدید نکند. به عبارت دیگر، هشت وزیر باید به نحوی چیده شوند که هیچ‌کدام در یک سطر، یک ستون یا یک قطر قرار نداشته باشند.

حل مسئله ۸ وزیر با الگوریتم SA در پایتون

در این فایل تنها یک سورس کد به نام SA.py وجود دارد که تمامی پارامترهای مربوط به الگوریتم تبرید شبیه سازی شده در این فایل قرار گرفته است. همچنین مسئله ی n وزیر (nQueen) با قابلیت تعیین تعداد وزیر در این سورس کد موجود است. این کار را می‌توانید با مراجعه به خط ۱۲۰ در همین سورس کد انجام دهید. تنها کافیست عدد موجود در سورس کد را تغییر دهید و مقدار جدیدی برای آن بنویسید تا برنامه مسئله را با آن تعداد وزیر که شما تعیین کرده اید حل کند.

الگوریتم SA از جمله آن الگوریتم ها می‌باشد که از قدرت بالایی در حل مسائل برخوردار است. به همین دلیل ما سورس کد حل مسئله ۸ وزیر به زبان پایتون را به کمک الگوریتم SA برایتان آماده کرده‌ایم. بخشی از سورس کد در زیر آورده شده است.

nQueen =20                              # Number Of Queens
MaxIt=100                               # Maximum Number of Iterations
MaxSubIt=10                             # Maximum Number of Sub-iterations
T0=0.025                                # Initial Temp.
alpha=0.99                              # Temp. Reduction Rate
nPop=3                                  # Population Size
nMove=5                                 # Number of Neighbors per Individual
nVar=nQueen                             # Number of Decision Variables

# Initialize the Positions and Costs
Positions = np.zeros((nPop, nVar))
Costs  = np.full(nPop, np.inf)
BestSolPos = np.zeros((1, nVar))
BestSolCost  = np.inf
for i in range(nPop):
    Positions[i,:] = np.random.permutation(nVar)
    Costs[i] = Fitness(Positions[i,:])
    if (Costs[i] <= BestSolCost):
         BestSolPos = Positions[i,:].copy()
         BestSolCost = Costs[i].copy()

تصویر خروجی حل مسئله

***  توجه  ***

قبل از اجرای سورس کد الگوریتم در محیط پایتون حتماً از نصب پکیج های مورد استفاده در این سورس کد در Python خود مطمئن شوید پکیج های استفاده شده در این سورس کد numpy و matplotlib می باشد که اولی پکیج مربوط به استفاده از آرایه ها و ماتریس ها در پایتون و دومی مربوط به عملیات های نموداری و Plot گرفتن می باشد. پیشنهاد ما نصب اسپایدر (Spyder (Python 3.7 می باشد که هم پایتون و پکیج های مختلف و هم IDE های مختلفی را همراه با امکان آپدیتشان نصب می کند.

درباره سورس کد حل مسئله ۸ وزیر با الگوریتم SA در پایتون

سورس کد حل مسئله ۸ وزیر با الگوریتم SA در پایتون عنوان اثری است که در این پست به آن پرداخته شده است. این سورس کد در پایتون ۳.۱۰ برنامه نویسی شده و بصورت کامل توسط گروه پشتیبانی پی استور تست و اجرا شده است.