تگ های موضوع سورس مسئله ۸ وزیر با الگوریتم ژنتیک به

مقدمه

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

الگوریتم ژنتیک

الگوریتم ژنتیک (GA) یک روش بهینه‌سازی مبتنی بر اصول انتخاب طبیعی و وراثت است. این الگوریتم‌ها به‌طور خاص برای حل مسائل پیچیده و غیرخطی طراحی شده‌اند. مراحل اصلی الگوریتم ژنتیک شامل:

1. ایجاد جمعیت اولیه: تعدادی از راه‌حل‌های ممکن به‌صورت تصادفی تولید می‌شوند.
   

1. محاسبه‌ی تناسب: هر راه‌حل براساس یک تابع تناسب (Fitness Function) ارزیابی می‌شود.
   

1. انتخاب: بر اساس تناسب، راه‌حل‌های بهتر انتخاب می‌شوند.
   

1. تقاطع: دو یا چند راه‌حل با یکدیگر ترکیب می‌شوند تا راه‌حل جدیدی تولید شود.
   

1. جهش: تغییرات تصادفی در برخی از راه‌حل‌ها اعمال می‌شود تا تنوع جمعیت حفظ شود.
   

پیاده‌سازی در سی شارپ

برای پیاده‌سازی این الگوریتم در زبان سی شارپ، مراحل زیر را دنبال می‌کنیم:

۱. تعریف کلاس‌ها

ابتدا باید کلاس‌هایی برای نمایندگی وزرا و جمعیت ایجاد کنیم. این کلاس‌ها شامل ویژگی‌هایی مانند موقعیت وزرا و تابع تناسب خواهند بود.
```csharp
public class Queen
{
public int Row { get; set; }
public int Column { get; set; }
public Queen(int row, int column)
{
Row = row;
Column = column;
}
}
public class Population
{
public List<Queen[]> Solutions { get; set; }
// متدهای دیگر برای مدیریت جمعیت
}
```

۲. تابع تناسب

تابع تناسب باید تعداد تداخلات بین وزرا را محاسبه کند. هر چه تعداد تداخلات کمتر باشد، تناسب بالاتر است.
```csharp
public int CalculateFitness(Queen[] queens)
{
int conflicts = 0;
// محاسبه تداخلات
return 28 - conflicts; // 28 بیشترین تداخلات ممکن برای 8 وزیر
}
```

۳. مراحل الگوریتم

در نهایت، مراحل الگوریتم را پیاده‌سازی می‌کنیم. از ایجاد جمعیت اولیه تا انتخاب، تقاطع و جهش همه در این مرحله انجام می‌شود.
```csharp
public void RunGeneticAlgorithm()
{
// ایجاد جمعیت اولیه
// محاسبه تناسب
// انتخاب، تقاطع و جهش تا رسیدن به راه‌حل بهینه
}
```

نتیجه‌گیری

حل مسئله هشت وزیر با استفاده از الگوریتم ژنتیک یکی از چالش‌برانگیزترین و جذاب‌ترین موضوعات در علم کامپیوتر است. با استفاده از زبان سی شارپ و پیاده‌سازی دقیق مراحل، می‌توانیم به راه‌حل‌های بهینه دست پیدا کنیم. این روش به ما امکان می‌دهد تا با استفاده از اصول زیستی، به حل مسائل پیچیده‌تر بپردازیم.

مقدمه‌ای بر مسئله هشت وزیر و الگوریتم ژنتیک در سی‌شارپ

مسئله هشت وزیر یکی از معروف‌ترین مسائل در حوزه بهینه‌سازی و الگوریتم‌های جستجو است. هدف در این مسئله، قرار دادن هشت وزیر بر روی صفحه شطرنج ۸x8 به گونه‌ای است که هیچ وزیری به دیگری حمله نکند. این مسئله، نمونه‌ای کلاسیک از مسائل n-ملکه است و به عنوان نمونه‌ای برای تست و توسعه الگوریتم‌های جستجو و بهینه‌سازی مورد استفاده قرار می‌گیرد.
استفاده از الگوریتم ژنتیک در حل این مسئله، روشی است مبتنی بر یادگیری و تقلید فرآیندهای طبیعی توسعه و انتخاب طبیعی. این الگوریتم، به جای جستجوی مستقیم، از جمعیت اولیه تصادفی شروع می‌کند و در هر نسل، بهترین راه‌حل‌ها را انتخاب و بر اساس آن‌ها استراتژی‌های جدید تولید می‌کند. در ادامه، جزئیات کامل این پیاده‌سازی در زبان سی‌شارپ را بررسی می‌کنیم.
ساختار کلی برنامه و مراحل پیاده‌سازی
۱. نمایش مسئله و کدگذاری راه‌حل‌ها
در اینجا، هر فرد (Chromosome) در جمعیت، یک آرایه است که نشان‌دهنده‌ی مکان قرارگیری هر وزیر است. مثلا، اگر آرایه `[0, 4, 7, 5, 2, 6, 1, 3]` باشد، نشان می‌دهد که وزیر اول در سطر 0 در ستون 0 است، وزیر دوم در سطر 1 در ستون 4، و به همین ترتیب.
۲. ایجاد جمعیت اولیه
در این مرحله، مجموعه‌ای از راه‌حل‌های تصادفی تولید می‌شود. تعداد این جمعیت، معمولاً وابسته به مسئله است (مثلاً 100 یا 200 راه‌حل). هر راه‌حل، یک آرایه تصادفی است که هر عنصر آن، نشان‌دهنده‌ی ستون قرارگیری وزیر در سطر مربوطه است.
۳. ارزیابی و محاسبه امتیاز (Fitness)
در این قسمت، هر راه‌حل بر اساس تعداد موارد حمله‌ی وزرا ارزیابی می‌شود. تعداد حمله‌ها، معیاری است برای سنجش کیفیت راه‌حل؛ هر چه تعداد حمله کمتر باشد، امتیاز بالاتری دارد.
۴. انتخاب والدین
بر مبنای امتیازهای محاسبه‌شده، راه‌حل‌های برتر انتخاب می‌شوند تا به عنوان والدین در نسل بعدی استفاده شوند. روش‌هایی مانند انتخاب چرخ‌پولی (Roulette Wheel) یا انتخاب تورنمنت رایج هستند.
۵. عملیات تولیدمثل (Crossover و Mutation)
در این مرحله، راه‌حل‌های جدید ساخته می‌شوند. عملیات کراس‌اوور ترکیب ویژگی‌های دو والد، و جهش (Mutation) تغییر تصادفی در برخی قسمت‌ها است تا تنوع جمعیت حفظ شود و از به‌هم‌ریختگی بیش از حد جلوگیری گردد.
۶. تکرار حلقه و توقف
این فرآیند تکرار می‌شود تا زمانی که یکی از شرایط توقف برآورده شود؛ مثلا، پیدا کردن راه‌حلی با صفر حمله یا رسیدن به تعداد نسل مشخص.
---

نمونه کد کامل پیاده‌سازی الگوریتم ژنتیک برای مسئله ۸ وزیر در سی‌شارپ

```csharp
using System;
using System.Collections.Generic;
using System.Linq;
namespace EightQueensGenetic
{
class Program
{
static Random rand = new Random();
// Parameters
const int populationSize = 100;
const int maxGenerations = 1000;
const double mutationRate =

1. 05;
   

static void Main(string[] args)
{
List<int[]> population = GenerateInitialPopulation();
int generation = 0;
int bestFitness = int.MaxValue;
int[] bestSolution = null;
while (generation < maxGenerations)
{
// ارزیابی جمعیت
var fitnessScores = population.Select(p => new { Solution = p, Fitness = CalculateFitness(p) }).ToList();
// بهترین راه‌حل در هر نسل
var currentBest = fitnessScores.OrderBy(x => x.Fitness).First();
if (currentBest.Fitness == 0)
{
bestSolution = currentBest.Solution;
break;
}
if (currentBest.Fitness < bestFitness)
{
bestFitness = currentBest.Fitness;
bestSolution = currentBest.Solution;
}
// انتخاب والدین
var parents = SelectParents(fitnessScores);
// تولید نسل جدید
population = GenerateNewPopulation(parents);
generation++;
}
// نمایش نتیجه
Console.WriteLine($"تعداد نسل: {generation}");
Console.WriteLine($"بهترین راه‌حل با حمله‌های: {bestFitness}");
PrintSolution(bestSolution);
}
static List<int[]> GenerateInitialPopulation()
{
var pop = new List<int[]>();
for (int i = 0; i < populationSize; i++)
{
var individual = new int[8];
var columns = Enumerable.Range(0, 8).ToList();
for (int row = 0; row < 8; row++)
{
int index = rand.Next(columns.Count);
individual[row] = columns[index];
columns.RemoveAt(index);
}
pop.Add(individual);
}
return pop;
}
static int CalculateFitness(int[] solution)
{
int conflicts = 0;
for (int i = 0; i < solution.Length; i++)
{
for (int j = i + 1; j < solution.Length; j++)
{
if (solution[i] == solution[j] || Math.Abs(solution[i] - solution[j]) == Math.Abs(i - j))
conflicts++;
}
}
return conflicts;
}
static List<int[]> SelectParents(List<dynamic> fitnessScores)
{
// روش تورنمنت
var parents = new List<int[]>();
for (int i = 0; i < populationSize; i++)
{
var tournament = new List<dynamic>();
for (int j = 0; j < 5; j++)
{
tournament.Add(fitnessScores[rand.Next(fitnessScores.Count)]);
}
var winner = tournament.OrderBy(x => x.Fitness).First();
parents.Add(winner.Solution);
}
return parents;
}
static List<int[]> GenerateNewPopulation(List<int[]> parents)
{
var newPop = new List<int[]>();
while (newPop.Count < populationSize)
{
var parent1 = parents[rand.Next(parents.Count)];
var parent2 = parents[rand.Next(parents.Count)];
var child1 = new int[8];
var child2 = new int[8];
// کراس‌اوور یک نقطه‌ای
int crossoverPoint = rand.Next(1, 8);
for (int i = 0; i < 8; i++)
{
if (i < crossoverPoint)
{
child1[i] = parent1[i];
child2[i] = parent2[i];
}
else
{
child1[i] = parent2[i];
child2[i] = parent1[i];
}
}
// جهش
if (rand.NextDouble() < mutationRate)
{
Mutate(child1);
}
if (rand.NextDouble() < mutationRate)
{
Mutate(child2);
}
newPop.Add(child1);
if (newPop.Count < populationSize)
newPop.Add(child2);
}
return newPop;
}
static void Mutate(int[] individual)
{
int index = rand.Next(8);
int newValue;
do
{
newValue = rand.Next(8);
} while (individual.Contains(newValue));
individual[index] = newValue;
}
static void PrintSolution(int[] solution)
{
for (int i = 0; i < 8; i++)
{
for (int j = 0; j < 8; j++)
{
if (solution[i] == j)
Console.Write("Q ");
else
Console.Write(". ");
}
Console.WriteLine();
}
}
}
}
```

نکات مهم و توضیحات

- کدگذاری راه‌حل: در اینجا، هر فرد یک آرایه از 8 عدد است که نشان‌دهنده‌ی ستون قرارگیری هر وزیر است.
- محاسبه امتیاز (Fitness): تعداد موارد حمله‌ی وزرا محاسبه می‌شود؛ هر چه کمتر باشد، راه‌حل بهتر است.
- انتخاب والدین: روش تورنمنت برای انتخاب راه‌حل‌های برتر استفاده شده است.
- کراس‌اوور و جهش: عملیات کراس‌اوور در یک نقطه انجام می‌شود و جهش، تغییر تصادفی در یک ژن است.
- توقف الگوریتم: زمانی که راه‌حلی با تعداد حمله صفر پیدا شود، یا حداکثر تعداد نسل برسد، فرآیند متوقف می‌شود.
این کد نمونه، نشان می‌دهد که چطور با ترکیب استراتژی‌های مختلف، می‌توان مسئله پیچیده‌ای مانند هشت وزیر را با الگوریتم ژنتیک حل کرد. در عمل، می‌توان این روش را برای مسائل بزرگ‌تر و پیچیده‌تر هم توسعه داد، البته با تغییر پارامترها و استراتژی‌های بهبود یافته.
اگر خواستید، می‌توانم توضیحات بیشتری در مورد هر بخش یا بهبودهای احتمالی ارائه دهم.