الگوریتم ژنتیک: کاربرد ها، مزایا، معایب و مثال ها به زبان ساده و جامع

الگوریتم ژنتیک چیست؟

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

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

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

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

متقاطع یا نوترکیبی یک عملگر ژنتیکی است که در آن دو فرد منتخب اطلاعات ژنتیکی را برای ایجاد فرزندان مبادله می کنند. این عمل شبیه تولیدمثل جنسی است که با ترکیب مواد ژنتیکی از هر دو والدین برای تولید فرزندان متنوع است.

جهش تغییرات تصادفی کوچکی را در اطلاعات ژنتیکی افراد انتخاب شده ایجاد می کند. این عملیات تنوع ژنتیکی را در جمعیت حفظ می کند و امکان کاوش در مناطق مختلف فضای محلول را فراهم می کند.

پس از اعمال عملگرهای ژنتیکی، جمعیت جدیدی جایگزین نسل قبلی می شود. این فرآیند برای تعداد ثابتی از نسل ها یا تا زمانی که یک شرط خاتمه برآورده شود، تکرار می شود، مانند دستیابی به سطح تناسب اندام مورد نظر یا تجاوز از تعداد مشخصی از تکرارها.

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

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

الگوریتم های ژنتیک چگونه کار می کنند

بیایید در مورد نحوه عملکرد الگوریتم های ژنتیک (GAs) با استفاده از مثالی از بهینه سازی یک کار رایج صحبت کنیم: پیدا کردن بهترین مسیر از خانه تا محل کار.

تصور کنید می خواهید کوتاه ترین مسیر را برای رفت و آمد روزانه خود پیدا کنید. شما می توانید از یک GA برای کمک به شما در این فرآیند بهینه سازی استفاده کنید.

رمزگذاری راه حل ها

– مسیرهای بالقوه را به عنوان جابجایی شهرها یا مکان ها نشان دهید.

– به عنوان مثال، از یک رشته از شناسه های شهر مانند “A-B-C-D-E-F” استفاده کنید، جایی که هر حرف نشان دهنده یک مکان است.

راه اندازی اولیه

– ایجاد یک جمعیت اولیه از مسیرهای بالقوه، به صورت تصادفی یا با استفاده از مسیرهای موجود.

ارزیابی

– هر مسیر را بر اساس عواملی مانند مسافت، شرایط ترافیکی و زمان سفر ارزیابی کنید.

– از یک تابع ارزیابی برای تعیین کمیت کیفیت هر مسیر استفاده کنید.

انتخاب

– مسیرهایی را برای نسل بعدی انتخاب کنید و از مسیرهایی که ارزش های ارزیابی کمتری دارند (راه حل های بهتر) استفاده کنید.

– روش های انتخاب ممکن است شامل انتخاب مسابقات، انتخاب چرخ رولت یا انتخاب بر اساس رتبه باشد.

کراس اوور

– ترکیب مواد ژنتیکی از دو مسیر اصلی برای ایجاد مسیرهای جدید.

– به عنوان مثال، بخش هایی از مسیرها را برای تشکیل مسیرهای فرزندان جدید مبادله کنید.

جهش

– ایجاد تغییرات تصادفی در مسیرها برای کشف احتمالات جدید و جلوگیری از گیر افتادن در Optima محلی.

– جهش ها می تواند شامل تعویض شهرها، درج شهرهای جدید یا تغییر ترتیب چند شهر باشد.

تولیذ نسل جدید:

– فرزندان حاصل از متقاطع و جهش، همراه با چند فرد مناسب از نسل قبلی، جمعیت جدید را برای تکرار بعدی تشکیل می دهند.

فسخ:

– روند را برای تعداد ثابتی از نسل ها یا تا زمانی که یک معیار خاتمه برآورده شود، مانند رسیدن به یک راه حل رضایت بخش، ادامه دهید.

راه حل نهایی:

– هنگامی که GA خاتمه می یابد، بهترین راه حل، معمولاً مسیری با کمترین ارزش ارزیابی، نشان دهنده مسیر بهینه یا نزدیک به بهینه برای رفت و آمد روزانه شما است.

با اعمال مکرر انتخاب، متقاطع و جهش، GAها جمعیت مسیرها را کشف و تکامل می‌دهند و به تدریج به سمت کوتاه‌ترین و کارآمدترین مسیر همگرا می‌شوند.

توجه: GAها به تنظیمات پارامتر مناسب (اندازه جمعیت، استراتژی انتخاب و غیره) نیاز دارند تا اکتشاف و بهره برداری را متعادل کنند.

کاربردهای الگوریتم ژنتیک

الگوریتم های ژنتیک در زمینه های مختلف کاربرد پیدا می کنند:

مشکلات بهینه سازی

– حل مسائلی مانند بهینه سازی تابع ریاضی، تنظیم پارامتر، بهینه سازی پورتفولیو و تخصیص منابع.

بهینه سازی ترکیبی

– حل مشکلاتی مانند مشکل فروشنده دوره گرد (TSP)، مشکل مسیریابی وسیله نقلیه (VRP)، زمان بندی کار، بسته بندی سطل زباله، و تراز توالی DNA.

یادگیری ماشینی

– مدل های یادگیری ماشین را با تنظیم فراپارامترها و انتخاب ویژگی ها بهینه کنید.

رباتیک تکاملی

– رفتار ربات و استراتژی های کنترل را تکامل دهید.

پردازش تصویر و سیگنال

– بهینه سازی بازسازی تصویر، حذف نویز و استخراج ویژگی.

طراحی و خلاقیت

– ایجاد طرح های هنری، ترکیبات موسیقی، و طرح های بازی.

مدل سازی مالی

– تخصیص پورتفولیو، معاملات الگوریتمی و مدیریت ریسک را بهینه کنید.

مثال هایی از الگوریتم های ژنتیک

شرکت های مختلف با موفقیت از الگوریتم های ژنتیک در حوزه های مختلف استفاده کرده اند:

DeepMind گوگل

– از GAها در پروژه AlphaFold برای توسعه یک الگوریتم تاشو پروتئین استفاده کرد.

تسلا

– پیاده سازی GA در فناوری رانندگی خودمختار برای بهینه سازی شبکه های عصبی.

آمازون

– اهرم GA برای بهینه سازی انجام سفارش و عملیات لجستیک.

Autodesk

– گنجاندن GA در نرم افزار طراحی برای کارهای بهینه سازی.

Uber

– بهینه ساز تکاملی را با استفاده از GAs توسعه داد تا کارایی سیستم قیمت گذاری پویا خود را افزایش دهد.

بوئینگ

– استفاده از GA برای بهینه سازی طراحی بال در پروژه های هواپیما.

فورد

– GAهای کاربردی برای بهینه سازی مسیریابی وسایل نقلیه برای ساده کردن عملیات لجستیک.

زیمنس

– استفاده از GA برای بهینه سازی فرآیند تولید برای بهبود کارایی تولید.

NVIDIA

– استفاده از GA برای بهینه سازی معماری GPU برای افزایش عملکرد در برنامه های کاربردی هوش مصنوعی و بازی.

تویوتا

– استفاده از GA برای بهینه سازی زنجیره تامین جهانی برای برنامه های تولید، مسیرهای لجستیکی و مدیریت موجودی.

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

نمونه مسئله و راه حل با الگوریتم ژنتیک

هدف ایجاد رشته هدف از یک رشته تولید شده به طور تصادفی با طول مساوی است. در این پیاده سازی از قیاس های زیر استفاده می شود:

– کاراکترهای A-Z، a-z، ۰-۹ و سایر نمادهای خاص به عنوان ژن در نظر گرفته می شوند.

– رشته ای که توسط این کاراکترها تشکیل می شود، کروموزوم، محلول یا فرد نامیده می شود.

– امتیاز تناسب اندام با تعداد کاراکترهایی که با آنهایی که در رشته هدف در یک شاخص خاص متفاوت است تعیین می شود. بنابراین، افراد با ارزش تناسب اندام پایین تر مورد علاقه هستند.

				
					// C++ program to create target string, starting from 
// random string using Genetic Algorithm 

#include <bits/stdc++.h> 
using namespace std; 

// Number of individuals in each generation 
#define POPULATION_SIZE 100 

// Valid Genes 
const string GENES = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOP"\ 
"QRSTUVWXYZ 1234567890, .-;:_!\"#%&/()=?@${[]}"; 

// Target string to be generated 
const string TARGET = "I love GeeksforGeeks"; 

// Function to generate random numbers in given range 
int random_num(int start, int end) 
{ 
	int range = (end-start)+1; 
	int random_int = start+(rand()%range); 
	return random_int; 
} 

// Create random genes for mutation 
char mutated_genes() 
{ 
	int len = GENES.size(); 
	int r = random_num(0, len-1); 
	return GENES[r]; 
} 

// create chromosome or string of genes 
string create_gnome() 
{ 
	int len = TARGET.size(); 
	string gnome = ""; 
	for(int i = 0;i<len;i++) 
		gnome += mutated_genes(); 
	return gnome; 
} 

// Class representing individual in population 
class Individual 
{ 
public: 
	string chromosome; 
	int fitness; 
	Individual(string chromosome); 
	Individual mate(Individual parent2); 
	int cal_fitness(); 
}; 

Individual::Individual(string chromosome) 
{ 
	this->chromosome = chromosome; 
	fitness = cal_fitness(); 
}; 

// Perform mating and produce new offspring 
Individual Individual::mate(Individual par2) 
{ 
	// chromosome for offspring 
	string child_chromosome = ""; 

	int len = chromosome.size(); 
	for(int i = 0;i<len;i++) 
	{ 
		// random probability 
		float p = random_num(0, 100)/100; 

		// if prob is less than 0.45, insert gene 
		// from parent 1 
		if(p < 0.45) 
			child_chromosome += chromosome[i]; 

		// if prob is between 0.45 and 0.90, insert 
		// gene from parent 2 
		else if(p < 0.90) 
			child_chromosome += par2.chromosome[i]; 

		// otherwise insert random gene(mutate), 
		// for maintaining diversity 
		else
			child_chromosome += mutated_genes(); 
	} 

	// create new Individual(offspring) using 
	// generated chromosome for offspring 
	return Individual(child_chromosome); 
}; 


// Calculate fitness score, it is the number of 
// characters in string which differ from target 
// string. 
int Individual::cal_fitness() 
{ 
	int len = TARGET.size(); 
	int fitness = 0; 
	for(int i = 0;i<len;i++) 
	{ 
		if(chromosome[i] != TARGET[i]) 
			fitness++; 
	} 
	return fitness;	 
}; 

// Overloading < operator 
bool operator<(const Individual &ind1, const Individual &ind2) 
{ 
	return ind1.fitness < ind2.fitness; 
} 

// Driver code 
int main() 
{ 
	srand((unsigned)(time(0))); 

	// current generation 
	int generation = 0; 

	vector<Individual> population; 
	bool found = false; 

	// create initial population 
	for(int i = 0;i<POPULATION_SIZE;i++) 
	{ 
		string gnome = create_gnome(); 
		population.push_back(Individual(gnome)); 
	} 

	while(! found) 
	{ 
		// sort the population in increasing order of fitness score 
		sort(population.begin(), population.end()); 

		// if the individual having lowest fitness score ie. 
		// 0 then we know that we have reached to the target 
		// and break the loop 
		if(population[0].fitness <= 0) 
		{ 
			found = true; 
			break; 
		} 

		// Otherwise generate new offsprings for new generation 
		vector<Individual> new_generation; 

		// Perform Elitism, that mean 10% of fittest population 
		// goes to the next generation 
		int s = (10*POPULATION_SIZE)/100; 
		for(int i = 0;i<s;i++) 
			new_generation.push_back(population[i]); 

		// From 50% of fittest population, Individuals 
		// will mate to produce offspring 
		s = (90*POPULATION_SIZE)/100; 
		for(int i = 0;i<s;i++) 
		{ 
			int len = population.size(); 
			int r = random_num(0, 50); 
			Individual parent1 = population[r]; 
			r = random_num(0, 50); 
			Individual parent2 = population[r]; 
			Individual offspring = parent1.mate(parent2); 
			new_generation.push_back(offspring); 
		} 
		population = new_generation; 
		cout<< "Generation: " << generation << "\t"; 
		cout<< "String: "<< population[0].chromosome <<"\t"; 
		cout<< "Fitness: "<< population[0].fitness << "\n"; 

		generation++; 
	} 
	cout<< "Generation: " << generation << "\t"; 
	cout<< "String: "<< population[0].chromosome <<"\t"; 
	cout<< "Fitness: "<< population[0].fitness << "\n"; 
}

				
					# Python3 program to create target string, starting from 
# random string using Genetic Algorithm 

import random 

# Number of individuals in each generation 
POPULATION_SIZE = 100

# Valid genes 
GENES = '''abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOP 
QRSTUVWXYZ 1234567890, .-;:_!"#%&/()=?@${[]}'''

# Target string to be generated 
TARGET = "I love GeeksforGeeks"

class Individual(object): 
	''' 
	Class representing individual in population 
	'''
	def __init__(self, chromosome): 
		self.chromosome = chromosome 
		self.fitness = self.cal_fitness() 

	@classmethod
	def mutated_genes(self): 
		''' 
		create random genes for mutation 
		'''
		global GENES 
		gene = random.choice(GENES) 
		return gene 

	@classmethod
	def create_gnome(self): 
		''' 
		create chromosome or string of genes 
		'''
		global TARGET 
		gnome_len = len(TARGET) 
		return [self.mutated_genes() for _ in range(gnome_len)] 

	def mate(self, par2): 
		''' 
		Perform mating and produce new offspring 
		'''

		# chromosome for offspring 
		child_chromosome = [] 
		for gp1, gp2 in zip(self.chromosome, par2.chromosome):	 

			# random probability 
			prob = random.random() 

			# if prob is less than 0.45, insert gene 
			# from parent 1 
			if prob < 0.45: 
				child_chromosome.append(gp1) 

			# if prob is between 0.45 and 0.90, insert 
			# gene from parent 2 
			elif prob < 0.90: 
				child_chromosome.append(gp2) 

			# otherwise insert random gene(mutate), 
			# for maintaining diversity 
			else: 
				child_chromosome.append(self.mutated_genes()) 

		# create new Individual(offspring) using 
		# generated chromosome for offspring 
		return Individual(child_chromosome) 

	def cal_fitness(self): 
		''' 
		Calculate fitness score, it is the number of 
		characters in string which differ from target 
		string. 
		'''
		global TARGET 
		fitness = 0
		for gs, gt in zip(self.chromosome, TARGET): 
			if gs != gt: fitness+= 1
		return fitness 

# Driver code 
def main(): 
	global POPULATION_SIZE 

	#current generation 
	generation = 1

	found = False
	population = [] 

	# create initial population 
	for _ in range(POPULATION_SIZE): 
				gnome = Individual.create_gnome() 
				population.append(Individual(gnome)) 

	while not found: 

		# sort the population in increasing order of fitness score 
		population = sorted(population, key = lambda x:x.fitness) 

		# if the individual having lowest fitness score ie. 
		# 0 then we know that we have reached to the target 
		# and break the loop 
		if population[0].fitness <= 0: 
			found = True
			break

		# Otherwise generate new offsprings for new generation 
		new_generation = [] 

		# Perform Elitism, that mean 10% of fittest population 
		# goes to the next generation 
		s = int((10*POPULATION_SIZE)/100) 
		new_generation.extend(population[:s]) 

		# From 50% of fittest population, Individuals 
		# will mate to produce offspring 
		s = int((90*POPULATION_SIZE)/100) 
		for _ in range(s): 
			parent1 = random.choice(population[:50]) 
			parent2 = random.choice(population[:50]) 
			child = parent1.mate(parent2) 
			new_generation.append(child) 

		population = new_generation 

		print("Generation: {}\tString: {}\tFitness: {}".\ 
			format(generation, 
			"".join(population[0].chromosome), 
			population[0].fitness)) 

		generation += 1

	
	print("Generation: {}\tString: {}\tFitness: {}".\ 
		format(generation, 
		"".join(population[0].chromosome), 
		population[0].fitness)) 

if __name__ == '__main__': 
	main()

خروجی

Generation: 1    String: tO{"-?=jH[k8=B4]Oe@}    Fitness: 18
Generation: 2    String: tO{"-?=jH[k8=B4]Oe@}    Fitness: 18
Generation: 3    String: .#lRWf9k_Ifslw #O$k_    Fitness: 17
Generation: 4    String: .-1Rq?9mHqk3Wo]3rek_    Fitness: 16
Generation: 5    String: .-1Rq?9mHqk3Wo]3rek_    Fitness: 16
Generation: 6    String: A#ldW) #lIkslw cVek)    Fitness: 14
Generation: 7    String: A#ldW) #lIkslw cVek)    Fitness: 14
Generation: 8    String: (, o x _x%Rs=, 6Peek3   Fitness: 13
                           . 
                           . 
                           . 
Generation: 29    String: I lope Geeks#o, Geeks   Fitness: 3
Generation: 30    String: I loMe GeeksfoBGeeks    Fitness: 2
Generation: 31    String: I love Geeksfo0Geeks    Fitness: 1
Generation: 32    String: I love Geeksfo0Geeks    Fitness: 1
Generation: 33    String: I love Geeksfo0Geeks    Fitness: 1
Generation: 34    String: I love GeeksforGeeks    Fitness: 0

توجه: الگوریتم هر بار با رشته های تصادفی شروع می شود، بنابراین خروجی ممکن است متفاوت باشد.

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