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

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

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

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

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

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

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

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

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

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

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

الگوریتم SA از جمله آن الگوریتم ها می باشد که از قدرت بالایی در حل مسائل برخوردار است. به همین دلیل ما سورس کد حل مسئله 8 وزیر به زبان پایتون را به کمک الگوریتم 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 های مختلفی را همراه با امکان آپدیتشان نصب می کند.

درباره سورس کد

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

مباحث مرتبط با الگوریتم SA

سورس کدهای آماده حل مسئله 8 وزیر