وبلاگ چت روم کامپیوتر و شبکه در سایت الفور
مفهوم منطق فازی (Fuzzy logic) اولین بار در پی تنظیم نظریه مجموعه‌های فازی به وسیله پروفسور لطفی زاده (1965 م) در صحنه محاسبات نو ظاهر شد.
دانش مورد نیاز برای بسیاری از مسائل مورد مطالعه به دو صورت متمایز ظاهر می‌شود:
1. دانش عینی مثل مدل‌ها، و معادلات، و فورمول‌های ریاضی که از پیش تنظیم شده و برای حل و فصل مسائل معمولی فیزیک، شیمی، یا مهندسی مورد استفاده قرار می‌گیرد.
2. دانش شخصی مثل دانستنی‌هایی که تا حدودی قابل توصیف و بیان زبان‌شناختی بوده، ولی، امکان کمی کردن آنها با کمک ریاضیات سنتی معمولاً وجود ندارد.
از آن جا که در عمل هر دو نوع دانش مورد نیاز است منطق فازی می‌کوشد آنها را به صورتی منظم، منطقی، و ریاضیاتی بایکدیگر هماهنگ گرداند.
منطق فازی از جمله منطق‌های چندارزشی بوده، و بر نظریه مجموعه‌های فازی تکیه می‌کند. مجموعه‌های فازی خود از تعمیم و گسترش مجموعه‌های قطعی به صورتی طبیعی حاصل می‌آیند.
مجموعه‌های قطعی (Crisp sets) در واقع همان مجموعه‌های عادی و معمولی هستند که در ابتدای نظریه کلاسیک مجموعه‌ها معرفی می‌شوند. افزودن صفت قطعی به واقع وجه تمایزی را ایجاد می‌نماید که به کمک آن می‌شود یکی از مفاهیم ابتکاری و حیاتی در منطق فازی موسوم به تابع عضویت را به آسانی در ذهن به وجود آورد.
در حالت مجموعه‌های قطعی، تابع عضویت فقط دو مقدار در برد خود دارد:
آری و خیر (یک و صفر) که همان دو مقدار ممکن در منطق دوارزشی کلاسیک هستند. بنابراین:
که در اینجا 
تابع عضویت عنصر x در مجموعه قطعی A است.
برد تابع عضویت از {0,1} در مورد مجموعه‌های قطعی به بازه بسته [0,1] برای مجموعه‌های فازی تبدیل می‌شود.
متغیرهای زبانی به متغیرهایی گفته می‌شود که مقادیر مورد قبول برای آنها به جای اعداد، کلمات و جملات زبانهای انسانی یا ماشینی هستند. همچنین که در محاسبات ریاضی از متغیرهای عددی استفاده میگردد در منطق فازی نیز از متغیرهای زبانی (گفتاری یا غیر عددی) استفاده میگردد متغیرهای زبانی بر اساس ارزشهای زبانی (گفتاری) که در مجموعه عبارت(کلمات /اصطلاحات) قرار دارند بیان می‌شود:عبارت زبانی(گفتاری Linguistic terms) صفاتی برای متغیرهای زبانی هستند. به عنوان مثال متغیر زبانی «سن» بسته به تقسیمات مورد نظرشخصی وشرایط می‌تواند مجموعه عبارت از قبیل «نوجوان»، «جوان»، «میان سال»، «سالمند» باشد: مجموعه عبارات (اصطلاحات)فازی (سن) = { «جوان»، «نه جوان»، «نه چندان جوان»، «خیلی جوان»، ...، «میان سال»، «نه چندان میان سال»، ...، «پیر»، «نه پیر»، «خیلی پیر»، «کم و بیش پیر»، ...، «نه خیلی جوان و نه خیلی پیر»، «نه جوان و نه پیر»... }
یا مثال دیگر، فشار(خون) را می‌شود متغیری زبانی در نظر گرفت، که ارزشهای (خصوصیت‌های)از قبیل پایین، بالا، ضعیف، متوسط، و قوی را می‌تواند در خود جای دهد. به زبان ریاضی داریم (T = Terms):
{پایین، بالا، ضعیف، متوسط، قوی} = (فشار)T
صفت عدم قطعیت، به صور گوناگون، در همه زمینه‌ها و پدیده‌ها صرف نظر از روش شناسی مورد کاربرد جهت مطالعه، طراحی، و کنترل پدیدار می‌شود.
برای مقابله مؤثر با پیچیدگی روزافزون در بررسی، مطالعه، مدل‌سازی، و حل مسائل جدید در فیزیک، مهندسی، پزشکی، زیست شناسی، و بسیاری از امور گوناگون دیگر ایجاد و ابداع روشهای محاسباتی جدیدی مورد نیاز شده‌است که بیشتر از پیش به شیوه‌های تفکر و تعلم خود انسان نزدیک باشد. هدف اصلی آنست که تا حد امکان، رایانه‌ها بتوانند مسائل و مشکلات بسیار پیچیده علمی را با همان سهولت و شیوایی بررسی و حل و فصل کنند که ذهن انسان قادر به ادراک و اخذ تصمیمات سریع و مناسب است.
در جهان واقعیات، بسیاری از مفاهیم را آدمی به صورت فازی (fuzzy به معنای غیر دقیق، ناواضح، و مبهم) درک می‌کند و به کار می‌بندد. به عنوان نمونه، هر چند کلمات و مفاهیمی همچون گرم، سرد، بلند، کوتاه، پیر، جوان، و نظائر اینها به عدد خاص و دقیقی اشاره ندارند، ذهن انسان با سرعت و با انعطاف پذیری شگفت‌آوری همه را میفهمد و در تصمیمات و نتیجه گیریهای خود به حساب می‌گیرد. این، در حالی ست که ماشین فقط اعداد را میفهمد و اهل دقّت است. اهداف شیوه‌های نو در علوم کامپیوتر آن است که اولا رمز و راز اینگونه تواناییها را از انسان بیاموزد و سپس آنها را تا حد امکان به ماشین یاد بدهد.
قوانین علمی گذشته در فیزیک و مکانیک نیوتونی همه بر اساس منطق قدیم استوار گردیده‌اند. در منطق قدیم فقط دو حالت داریم: سفید و سیاه، آری و خیر، روشن و تاریک، یک و صفر، و درست و غلط. متغیرها در طبیعت یا در محاسبات بر دو نوعند: ارزشهای کمی که می‌توان با یک عدد معین بیان نمود و ارزشهای کیفی که براساس یک ویژگی بیان می‌شود. این دو ارزش قابل تبدیلند:
مثلا در مورد قد افراد با ارزش عددی (سانتی‌متر)اندازه‌گیری شود و افراد را به دسته‌های قدکوتاه و قدبلند تقسیم‌بندی کنیم و حد آستانه 180 سانتی‌متر برای قد بلندی مدنظر باشد. تمامی افراد زیر 180 سانتی متر براساس منطق قدیم قدکوتاهند حتی اگر قد فرد 179 سانتی‌متر باشد. ولی در مجموعه فازی هر یک از این صفات براساس تابع عضویت تعریف و بین صفر تا یک ارزشگذاری می‌شود. از آن جا که ذهن ما با منطق دیگری کارهایش را انجام می‌دهد و تصمیماتش را اتّخاذ می‌کند، جهت شروع، ایجاد و ابداع منطق‌های تازه و چندارزشی مورد نیاز است که منطق فازی یکی از آنها می‌باشد.
تفاوت نظریه فازی و نظریه احتمالات:
نوشته شده توسط لادن در دوشنبه 90/1/29 و ساعت 10:2 صبح | نظرات دیگران()شبکه‌های عصبی مصنوعی (Artificial Neural Network - ANN) یا به زبان ساده‌تر شبکه‌های عصبی سیستم‌ها و روشهای محاسباتی نوینی هستند برای یادگیری ماشینی، نمایش دانش، و در انتها اعمال دانش به دست آمده در جهت بیش‌بینی پاسخ‌های خروجی از سامانه‌های پیچیده. ایده اصلی این گونه شبکه‌ها (تا حدودی) الهام‌گرفته از شیوه کارکرد سیستم عصبی زیستی، برای پردازش داده‌ها، و اطلاعات به منظور یادگیری و ایجاد دانش قرار دارد. عنصر کلیدی این ایده، ایجاد ساختارهایی جدید برای سامانه پردازش اطلاعات است. این سیستم از شمار زیادی عناصر پردازشی فوق العاده بهم‌پیوسته با نام نورون تشکیل شده که برای حل یک مسأله با هم هماهنگ عمل می‌کند.
با استفاده از دانش برنامه‌نویسی رایانه می‌توان ساختار داده‌ای طراحی کرد که همانند یک نرون عمل نماید. سپس با ایجاد شبکه‌ای از این نورون‌های مصنوعی به هم پیوسته، ایجاد یک الگوریتم آموزشی برای شبکه و اعمال این الگوریتم به شبکه آن را آموزش داد.
این شبکه‌ها برای تخمین (Estimation) و تقریب (Approximation)کارایی بسیار بالایی از خود نشان داده اند. گستره کاربرد این مدل‌های ریاضی بر گرفته از عملکرد مغز انسان، بسیار وسیع می‌باشد که به عنوان چند نمونه کوچک می توان استفاده از این ابزار ریاضی در پردازش سیگنال‌های بیولوییکی، مخابراتی و الکترونیکی تا کمک در نجوم و فضا نوردی را نام برد.
اگر یک شبکه را هم‌ارز با یک گراف بدانیم، فرآیند آموزش شبکه تعیین نمودن وزن هر یال و bias اولیه خواهد.
نوشته شده توسط لادن در دوشنبه 90/1/29 و ساعت 9:51 صبح | نظرات دیگران()مسئله چند وزیر یک معمای شطرنجی و ریاضیاتی است که بر اساس آن باید n وزیر شطرنج در یک صفحه n×n شطرنج به‌گونه‌ای قرار داده شوند که هیچ‌یک زیر ضرب دیگری نباشند. با توجه به اینکه وزیر به‌صورت افقی، عمودی و اُریب حرکت می‌کند، باید هر وزیر را در طول، عرض و قطر متفاوتی قرار داد.
اولین و مشهورترین شکل این مسئله معمای هشت وزیر است که برای حل آن باید 8 وزیر را در یک صفحهً معمولی (8x8) شطرنج قرار داد. این مسئله 92 جواب دارد که 12 جواب آن منحصر به‌فرد است یعنی بقیه جواب‌ها از تقارن جوابهای اصلی به‌دست می‌آید.
مسئله n وزیر در صورتی جواب دارد که n مساوی 1 یا بیشتر از 3 باشد. یعنی مسئله دو وزیر و سه وزیر راه حلی ندارند.
این مسئله در سال 1848 توسط شطرنج بازی به نام Max Bezzel عنوان شد و ریاضی دانان بسیاری ازجمله Gauss و Georg Cantor بر روی این مسئله کار کرده و در نهایت آنرا به n وزیر تعمیم دادند. اولین راه حل توسط Franz Nauck در سال 1850 ارائه شد که به همان مسئله n وزیر تعمیم داده شد. پس از آن Gunther راه حلی با استفاده از دترمینان ارائه داد که J.W.L. Glaisher آنرا کامل نمود.در سال 1979، Edsger Dijkstra Nauck با استفاده از الگوریتم عقب گرد اول عمق، این مسئله را حل کرد.
هدف از مسئله n وزیر، چیدن n مهره وزیر در یک صفحه شطرنج(n*n) است، به طوری که هیچ دو وزیری یکدیگر را گارد ندهند، یعنی هیچ دو مهره‌ای نباید در یک سطر، ستون یا قطر یکسان باشند.وزیر در خانه‌های شطرنج به صورت عرضی، طولی و قطری می‌تواند حرکت کند. مسئله n وزیر از جمله مسائل NP در هوش مصنوعی است که روشهای جستجوی معمولی قادر به حل آنها نخواهد بود
از تکنیک عقبگرد Backtracking برای حل مسائلی استفاده می‌شود که در آنها دنباله‌ای از اشیاء از یک مجموعه مشخص انتخاب می‌شود، به طوری که این دنباله، ملاکی را در بر می‌گیرد.عقبگرد حالت اصلاح شده? جست و جوی عمقی یک درخت است.این الگوریتم همانند جست و جوی عمقی است، با این تفاوت که فرزندان یک گره فقط هنگامی ملاقات می‌شوند که گره امید بخش باشدو در آن گره حلی وجود نداشته باشد. با توجه به اینکه هیچ ? وزیری نباید همدیگر را گارد کنند و در یک سطر نمی‌توانند باشند، تعداد کل حالت‌ها برای n=? برابر ?*?*?*?=??? است. در شطرنج یک وزیر می‌تواند به مهره‌هایی که در خانه‌های عمود یا مورب به وی قرار دارند حمله کند. یا به عبارت ریاضی، اگر ردیفها و ستونهای شطرنج را از یک تا هشت شماره گذاری کنیم و وزیر در خانه (i, j) قرار داشته باشد، مهره‌هایی که در خانه‌های (i, m) یا (m, j) یا (i ± m, j ± m) قرار دارند توسط وزیر تهدید می‌شوند.
برای سادگی تشریح این مسئله با استفاده از روش بازگشت به عقب، فرض می‌کنیم که خانه‌های شطرنج 4x4و تعداد وزیرها نیز 4 باشد. سپس بعد از یافتن راه حل برای این مسئله ساده شده، اقدام به نوشتن الگوریتم برای مسئله اصلی می‌کنیم.
مراحل جستجو برای یافتن جواب را به این صورت دنبال می‌کنیم که: وزیر اول را در ردیف اول و ستون اول قرار میدهیم.
در ردیف دوم از اولین ستون به جلو رفته و به دنبال خانه‌ای می‌گردیم که مورد تهدید وزیر اول نباشد و وزیر دوم را در این خانه قرار میدهیم.
همانند قبل، در ردیف سوم از اولین ستون به جلو رفته و به دنبال خانه‌ای می‌گردیم که مورد تهدید وزیران اول و دوم نباشد. می‌بینیم که چنین خانه‌ای موجود نیست. پس به عقب یعنی ردیف دوم برگشته و وزیر دوم را به خانه‌ای دیگر از ردیف دوم منتقل می‌کنیم که مورد تهدید وزیر اول نباشد.
دوباره در ردیف سوم اولین خانه‌ای را میابیم که مورد تهدید دو وزیر قبلی نباشد. این بار خانه را می‌یابیم و وزیر سوم را در آن قرار میدهیم.
همانند قبل، در ردیف چهارم به دنبال اولین خانه‌ای می‌گردیم که مورد تهدید وزیران پیشین نباشد. چنین خانه‌ای موجود نیست. به ردیف قبل یعنی ردیف سوم باز می‌گردیم تا خانه‌ای دیگر برای وزیر سوم بیابیم. خانه دیگری وجود ندارد. به ردیف قبل یعنی ردیف دوم بر می‌گردیم تا خانه دیگری برای وزیر دوم پیدا کنیم. به آخرین ستون رسیده‌ایم و خانه دیگری نیست. به ردیف قبل یعنی ردیف اول بر می‌گردیم و وزیر اول را یک ستون به جلو می‌بریم.
در ردیف دوم اولین خانه‌ای را میابیم که مورد تهدید وزیر اول نباشد و وزیر دوم را در آن خانه قرار میدهیم.
در ردیف سوم اولین خانه‌ای را میابیم که مورد تهدید وزیران اول و دوم نباشد و وزیر سوم را در آن خانه می‌گذاریم.
در ردیف چهارم اولین خانه‌ای را میابیم که مورد تهدید وزیران پیشین نباشد. این بار خانه را می‌یابیم و وزیر چهارم را در آن خانه قرار میدهیم.
به یک جواب می‌رسیم. حال اگر فرض کنیم که این خانه جواب نیست و به مسیر خود ادامه دهیم، احتمالا" می‌توانیم جوابهای دیگری نیز بیابیم.
void queens ( index i)
{
index j;
if ( promising(i))
if ( i == n)
cout << col [1] through col [n];
else
for ( j = 1 ; j ≤ n ; j++ ) {
col [ i +? ] = j;
queens ( i + 1);
}
}
bool promising ( index i )
{
index k ;
bool switch;
k = ?;
switch = true ;
while ( k < i && switch ) {
if (col [i] == col[k] || abs(col[i] – col[k] == i-k)
switch = false;
k++;
}
return switch;
}
#include <stdio.h>
int b[?];
inline static int unsafe(int y) {
int i, t, x;
x = b[y];
for (i = ?; i <= y; i++) {
t = b[y - i];
if ( (t == x) ||
(t == x - i) ||
(t == x + i) ) {
return 1;
}
}
return 0;
}
static void putboard(void) {
static int s = ?;
int x, y;
printf("\n\nSolution #?i\n", ++s);
for (y = ?; y < ?; y++) {
for (x = ?; x < ?; x++) {
printf((b[y] == x) ? "|Q" : "|_");
}
printf("|\n");
}
}
int main(void) {
int y = 0;
b[?] = -1;
while (y >= 0) {
do {
b[y]++;
} while ((b[y] < 8) && unsafe(y));
if (b[y] < 8) {
if (y < 7) {
b[++y] = -1;
} else {
putboard();
}
} else {
y--;
}
}
return 0;
}
#include <assert.h>
#include <stdio.h>
#define MAXSIZE 8
class EightQueens
{
int m_size;
int m_solution_count;
int m_attempt_count;
int m_queen[MAXSIZE];
bool m_row_inuse[MAXSIZE];
bool m_diag_rise[MAXSIZE*2];
bool m_diag_fall[MAXSIZE*2];
public:
EightQueens(int size, bool is_alt) {
assert(size <= MAXSIZE);
m_size = size;
m_solution_count = 0;
m_attempt_count = 0;
for (int i = 0; i < m_size; i++) {
m_queen[i] = i;
m_row_inuse[i] = 0;
}
for (int j = 0; j < m_size*2; j++) {
m_diag_rise[j] = 0;
m_diag_fall[j] = 0;
}
if (is_alt) SearchAlt(0);
else Search(0);
}
int GetSolutionCount() {
return m_solution_count;
}
int GetAttemptCount() {
return m_attempt_count;
}
private:
void SearchAlt(int col){
if (col == m_size) {
m_solution_count++;
return;
}
for (int row = 0; row < m_size; row++) {
m_attempt_count++;
if (m_row_inuse[row] == 0 && IsDiagValid(col, row)) {
m_queen[col] = row;
m_row_inuse[row] = 1;
SetDiags(col, 1);
SearchAlt(col+1);
SetDiags(col, 0);
m_row_inuse[row] = 0;
m_queen[col] = -1;
}
}
}
void Search(int col) {
if (col == m_size) {
m_solution_count++;
return;
}
for (int i = col; i < m_size; i++) {
if (SwapQueenIfDiagValid(col, i)) {
Search(col+1);
UnSwapQueen(col, i);
}
}
}
void SwapQueenBasic(int i, int j) {
int hold = m_queen[i];
m_queen[i] = m_queen[j];
m_queen[j] = hold;
}
void SetDiags(int col, int val) {
assert(m_diag_rise[m_queen[col] + col] != val);
m_diag_rise[m_queen[col] + col] = val;
assert(m_diag_fall[m_queen[col] - col + m_size] != val);
m_diag_fall[m_queen[col] - col + m_size] = val;
}
bool IsDiagValid(int col, int row) {
return (m_diag_rise[row + col] == 0 &&
m_diag_fall[row - col + m_size] == 0);
}
bool SwapQueenIfDiagValid(int i, int j) {
m_attempt_count++;
if (IsDiagValid(i, m_queen[j])) {
SwapQueenBasic(i, j);
SetDiags(i, 1);
return true;
}
return false;
}
void UnSwapQueen(int i, int j) {
SetDiags(i, 0);
SwapQueenBasic(i, j);
}
};
void
do_work(bool is_alt)
{
int size = 8;
EightQueens puzzle(size, is_alt);
int soln = puzzle.GetSolutionCount();
int attempt = puzzle.GetAttemptCount();
assert(size != 8 || soln == 92);
const char* style = is_alt ? "cartesian" : "permutation";
printf("EightQueens[%d] has %d solutions found in %5d attempts using %s search.\n", size, soln, attempt, style);
}
int main()
{
printf("We should have 92 solutions for 8x8.\n");
do_work(0);
do_work(1);
}
از الگوریتم مونت کارلو برای برآورد کردن کارایی یک الگوریتم عقبگرد استفاده می‌شود.الگوریتمهای مونت کارلو، احتمالی هستند، یعنی دستور اجرایی بعدی گاه به طور تصادفی تعیین می‌شوند.در الگوریتم قطعی چنین چیزی رخ نمی‌دهد.الگوریتم مونت کارلو مقدار مورد انتظار یک متغیر تصادفی را که روی یک فضای ساده تعریف می‌شود، با استفاده از مقدار میانگین آن روی نمونه تصادفی از فضای ساده بر آورد می‌کند.تضمینی وجود ندارد که این برآورد به مقدار مورد انتظار واقعی نزدیک باشد، ولی احتمال نزدیک شدن آن، با افزایش زمان در دسترس برای الگوریتم، افزایش می‌یابد.
int ostimate _ n_ queens (int n)
{
index i , j , col [1..n];
int m , mprod , numnodes ;
set _of_ index prom _children;
i = 0;
numnodes =1 ;
m = 1;
mprod = 1;
while ( m != 0 && i != n ) {
mprod = mprod * m ;
numnodes = numnodes + mprod * n;
i ++;
m = 0 ;
prom_childern = Ø;
for ( j = 1 ; j ≤ n ; j++;) {
col [i] = j ;
if ( promising(i)) {
m++;
prom_children = prom _ children U {i};
}
}
if ( m != 0) {
j = random selection from prom _childeren;
col [i];
}
}
return numnodes;
}
برای حل این مسئله که دارای 92 جواب است، باید تکنیکهایی جهت کاهش حالات، روش Brute Force یا امتحان تک تک جواب‌ها انجام شود. تعداد همه حالاتی که می‌تواند در روش Brute Force چک شود برابر 16،777،216یا هشت به توان هشت است! یکی از روشهای حل این مسئله برای n>=4 یا n=1 استفاده از روش مکاشفه‌ای ( heuristic)است:
1- عدد n را بر عدد 12 تقسیم کن و باقی مانده را یادداشت کن
2- به ترتیب اعداد زوج 2 تا n را در لیستی بنویس
3- اگر باقی مانده 3 یا 9 بود، عدد 2? را به انتهای لیست انتقال بده.
4- به لیست اعداد فرد ? تا n را به ترتیب اضافه کن، اما اگر باقی مانده 8 بود اعداد را دو به دو باهم عوض کند (مثلا1و3و5و7و9 تبدیل به 3و1و5و7و9 میشه)
5- اگر باقی مانده 2 بود جای 1و3 را با هم عوض کن و 5 را به انتهای لیست ببر.
6- اگر باقی مانده 3 یا 9 بود، اعداد 1و 3را به انتهای لیست ببر.
7- حال با استفاده از لیست بدست آمده وزیرها در صفحه شطرنج چیده می‌شوند، بطوریکه جای وزیر ستون اول، اولین عدد لیست، جای وزیر ستون دوم، دومین عدد لیست و ...
این الگوریتم یک راه حل برای حل این مسئله‌است، برای بدست آوردن همه حالات از روشهای دیگری می‌توان استفاده کرد. روش حل مسئله 12 راه حل یکتا دارد که با در نظر گیری تقارن و چرخش به 99 حالت قابل تبدیل است.
می‌توان به مسئله 8 وزیر به عنوان یک مسئله بهینه سازی نیز نگریست که در آن هدف بهینه کردن تعداد گاردهای جفت وزیرها می‌باشد.
به عنوان مثال فرض کنید در صفحه شطرنج معمولی ،8 وزیر را به دو روش زیر قرار دهیم :
در روش چینش سمت چپ 3 وزیر و در روش چینش سمت راست 4وزیر همدیگر را گارد می‌دهند. بنابراین روش چینش قبلی بهینه تر از روش چینش فعلی است. در واقع می‌توان مسئله بهینه سازی را به صورت زیر تعریف کرد. فرض کنید S مجموعه همه جوابهای ممکن برای مسئله باشد. در صورتی S* می‌تواند جواب مسئله باشد که به ازای همه جوابهای موجود در S ، S* بهینه تر از دیگر جواب‌ها باشد. در مسئله 8وزیر دیدیم که جوابی بهینه‌است که تعداد گاردهای جفت وزیر آن کمتر باشد.
روشهای جستجوی محلی همگی حالت‌های همسایه حالت فعلی را برای رسیدن به بهینه‌ترین جواب بررسی می‌کنند. از این رو وجود دو تابع در همه این روشهای جستجو الزامی است. اولین تابع میزان بهینگی جواب مسئله ارزیابی می‌کند و تابع دوم یکی از حالت‌های همسایه حالت فعلی را انتخاب می‌کند.
نحوه پیاده سازی و طراحی الگوریتم برای انتخاب حالت هسایه در این روشهای جستجو از اهمیت ویژه‌ای برخوردار است. به عنوان مثال برای مسئله 8 وزیر می‌توان به شکل‌های زیر حالت‌های همسایگی را تولید کرد:
1) دو وزیر به تصادف انتخاب شده و جای آن دو باهم عوض گردد.
2) یکی از وزیرها به تصادف انتخاب شده و شماره سطر آن به تصادف تغییر کند.
3) ویزیری به تصادف انتخاب شده و یک خانه به سمت بالا یا پایین حرکت کند
Eight queens puzzle. (2010, May 3). In Wikipedia, The Free Encyclopedia. Retrieved 18:33, May 7, 2010,
نوشته شده توسط لادن در یکشنبه 90/1/28 و ساعت 3:49 عصر | نظرات دیگران()سامانه‌های خِبره یا سیستم‌های خِبره (Expert systems) به دسته‌ای خاص از نرم‌افزارهای رایانه‌ای اطلاق می‌شود که در راستای کمک به کاردانان و متخصّصان انسانی و یا جایگزینی جزئی آنان در زمینه‌های محدود تخصّصی تلاش دارند. اینگونه سامانه‌ها، در واقع، نمونه‌های ابتدایی و ساده‌تری از فن‌آوری پیش‌رفته‌تر سامانه‌های مبتنی بر دانش به حساب می‌آیند.
این سامانه‌ها معمولاً اطلاعات را به شکل واقعیات[1] و قواعد[2] در دادگانی به نام پایگاه دانش به شکل ساختار مند ذخیره نموده، و سپس با استفاده از روشهایی خاص استنتاج از این داده‌ها نتایج مورد نیاز حاصل می‌شود.
سامانه‌های تجربی موجبات انجام امور و یا تسهیل در انجام آنها را در زمینه‌های متنوّعی همچون پزشکی، حسابداری، کنترل فرایندها، منابع انسانی، خدمات مالی، و GIS فراهم می‌آورند. در هر یک از این زمینه‌ها می توان کارهایی از نوع راهنمایی، تحلیل، دسته‌بندی، مشاوره، طراحی، تشخیص، کاوش، پیش بینی، ایجاد مفاهیم، شناسایی، توجیه، یادگیری، مدیریت، کنترل، برنامه‌ریزی، زمان بندی و آزمایش را با مددجویی از سیستم‌های تجربی با سرعت و سهولت بیشتری به انجام رسانید. †
سیستم‌های تجربی یا به عنوان جایگزین فرد متخصص یا به عنوان کمک به وی استفاده می‌شوند.
نظام های خبره این امکان را در اختیار می گذارد تا بتوان دانش موجود در سطح جامعه را به صورت گسترده تر و کم هزینه تری اشاعه داد . این موضوع یعنی اشاعه دانش برای عموم مردم یکی از بنیادی ترین و اصلی ترین وظایف و رسالتهای حوزه کتابداری است .
مثلا از طریق واسطهای هوشمند جست و جوی اطلاعات می توان مهارتهای جستجوی پیشرفته را که اغلب خاص متخصصان با تجربه است در میان طیف وسیعی از کاربران در دسترس قرار دهد . سرعت استدلال یا حل مسائل در نظام های خبره می تواند منجر به ارائه خدمات موثرتر و سریع تر در برخی فعالیتهای کتابداری شود و انعطاف پذیری بیشتری را در پاسخگویی به نیازهای مخاطبان به وجود آورد.
کاربرد نظام های خبره و هوشمند را در حوزه های نمایه سازی، چکیده نویسی، طراحی و تولید اصطلاحنامه ها، فهرست نویسی، بازیابی متن فارغ از منطق بولی، بازیابی متون مبتنی بر منطق بولی، تجزیه و تحلیل خودکار محتوا و ارائه دانش، مدیریت و دسترسی به محتوی پایگاه های رابطه ای، اسناد هوشمند، تجزیه و تحلیل پایگاه های اطلاعاتی دانسته اند.
تا ابتدای دهه 1980 (م) کار چندانی در زمینه ساخت و ایجاد سامانه‌های خِبره توسط پژوهش گران هوش مصنوعی صورت نگرفته بود. از آن زمان به بعد، کارهای زیادی در این راستا و در دو حوزه? متفاوت ولی مرتبط سامانه‌های کوچک خبره و نیز سامانه‌های بزرگ خبره انجام شده است.
هوش مصنوعی: هوش مصنوعی روشی است در جهت هوشمند کردن کامپیوتر تا قادر باشد در هر لحظه تصمیم گیری کرده و اقدام به بررسی یک مسئله نماید. هوش مصنوعی، کامپیوتر را قادر به تفکر می‌کند و روش آموختن انسان را تقلید می نماید. بنابراین اقدام به جذب اطلاعات جدید جهت بکارگیری مراحل بعدی می پردازد.
مغز انسان به بخش هایی تقسیم شده است که هر بخش وظیفه خاص خود را جدا از بقیه انجام می دهد. اختلال در کار یک بخش تاثیری در دیگر قسمت‌های مغز نخواهد گذاشت. در برنامه‌های هوش مصنوعی نیز این مسئله رعایت می‌شود درحالی که در برنامه‌های غیر هوش مصنوعی مثل C یا Pascal تغییر در برنامه روی سایر قسمت‌های برنامه و اطلاعات تاثیر دارد.
مباحث کاربردی و مهم در تحقق یک سیستم هوش مصنوعی :
1-سیستم‌های خبره (Expert Systems)
2-شبکه‌های عصبی (Neural Network)
3- الگوریتمهای ژنتیک (Genetic Algorithms)
4- سیستم‌های منطق فازی (Fuzzy Logic Systems)
سیستم‌های خبره برنامه هایی هستند که رفتار یک انسان متخصص در یک زمینه بخصوص را تقلید می کنند. این برنامه از اطلاعاتی که استفاده کننده در آنها ذخیره می‌کند جهت اعلام یک عقیده در یک موضوع بخصوص استفاده می کند. از اینرو سیستم‌های خبره تا هنگامی که بتوانند موضوعی را که با پاسخ‌های شما مطابقت داشته باشد بیابند به سوال کردن از شما ادامه می دهند. به منظور درک کردن آنچه یک سیستم متخصص انجام می دهد مکالمه زیر که بین یک متخصص در امور میوه و فرد دیگری که می خواهد از وی توصیه ای در این مورد دریافت کند را در نظر بگیرید:
- متخصص: آیا میوه سبز است؟
- استفاده کننده: خیر.
- متخصص: آیا میوه قرمز است؟
- استفاده کننده: بله.
- متخصص: آیا این میوه روی درخت رشد می کند؟
- استفاده کننده: خیر.
- متخصص: آیا این میوه روی یک بوته رشد می کند؟
- استفاده کننده: بله.
- متخصص: آیا این بوته تیغ دارد؟
- استفاده کننده: بله.
- متخصص: این میوه تمشک است!
هدف از طراحی یک سیستم متخصص کامپیوتری در امر میوه تولید این مکالمه است. در حالت عمومی تر سیستم متخصص سعی می‌کند که به استفاده کننده از خود در مورد موضوعی که از آن مطلع است راهنمایی دهد.
مزایای یک سیستم خبره چیست؟
میزان مطلوب بودن یک سیستم خبره اصولا به میزان قابلیت دسترسی به آن و میزان سهولت کار با آن بستگی دارد.
می توان مزایایی که یک سیستم خبره در برابر انسان خبره دارد را به این صورت نام برد:
مثال هایی از سیستم‌های متخصص تجاری:
در اوایل دهه 80 سیستم‌های متخصص به بازار عرضه شد که می توانستند مشورت‌های مالیاتی، توصیه‌های بیمه ای و یا قانونی را به استفاده کنندگان خود ارائه دهند.
سیستم‌های متخصص چگونه کار می کنند؟
هر سیستم متخصص از دو بخش تشکیل می‌شود:
- بانک اطلاعاتی
- تولید کننده مکالمه
منظور از بانک اطلاعاتی در اینجا مکانیسم نگهداری اطلاعات و قوانین ویژه ای در مورد یک موضوع بخصوص می باشد. با این توصیف دو اصطلاح زیر تعریف می‌شود:
- شیء (): منظور از شیء در اینجا نتیجه ای است که با توجه به قوانین مربوط به آن تعریف می گردد.
- شاخص (Attribute): منظور از شاخص یا «صفت» یک کیفیت ویژه است که با توجه به قوانینی که برای آن در نظر گرفته شده است به شما در تعریف شیء یاری می دهد.
بنابراین می توان بانک اطلاعاتی را بصورت لیستی از اشیاء که در آن قوانین و شاخص‌های مربوط به هر شیء نیز ذکر شده است در نظر گرفته شود.
در ساده‌ترین حالت(که در اکثر کاربردها نیز همین حالت بکار می رود) قانونی که به یک شاخص اعمال می‌شود این مطلب را بیان می‌کند که آیا شیء مورد نظر شاخص دارد یا ندارد؟
یک سیستم متخصص که انواع مختلف میوه را شناسایی می‌کند احتمالاً دارای بانک اطلاعاتی به صورت زیر خواهد بود:
شیء قانون شاخص
سیب دارد روی درخت رشد می کند.
دارد گرد است
دارد رنگ قرمز یا زرد است
ندارد در کویر رشد می کند
انگور ----- -------------------
بانک ساده شده بالا، تنها با استفاده از قانون <<دارد>>:
| شیء | شاخص هایی که دارد |
|---|---|
| سیب | رشد روی درخت |
| سیب | گرد بودن |
| سیب | رنگ قرمز یا زرد |
| سیب | رشد نکردن در کویر |
تولید کننده مکالمهآن بخش از سیستم متخصص است که سعی می‌کند از اطلاعاتی که شما ذخیره کرده اید جهت یافتن یک شیء منطبق با خواسته شما استفاده نماید.
دو نوع عمده از تولید کننده‌های مکالمه وجود دارد:
برخی قوانین قطعی هستند. به عنوان مثال یک شیمیدان می تواند با قطعیت و یقین اعلام کند که اگر اتم مورد نظر دارای 2 الکترون باشد آنگاه این اتم به عنصر هلیم تعلق دارد. اکثر قوانین قطعی نیستند بلکه با یک درصد مشخص، احتمال وقوع آنها می رود. با این وجود در بسیاری از اینگونه موارد عامل عدم قطعیت از نظر آماری اهمیت چندانی ندارد و از این رو شما می توانید با این قوانین بصورت قوانین جبری برخورد کنید.
در رابطه با این دو گروه عمده(یعنی قطعی و عدم قطعی) سه روش اساسی برای ساخت «تولید کننده مکالمه» وجود دارد:
تفاوت بین این سه روش به شیوه ای که «تولید کننده مکالمه» توسط آن سعی می‌کند به هدف خود برسد، بستگی دارد.
نوشته شده توسط لادن در جمعه 90/1/26 و ساعت 10:20 صبح | نظرات دیگران()الگوریتم ژنتیک (Genetic Algorithm - GA) تکنیک جستجویی در علم رایانه برای یافتن راه‌حل تقریبی برای بهینه‌سازی و مسائل جستجو است. الگوریتم ژنتیک نوع خاصی از الگوریتمهای تکامل است که از تکنیکهای زیست‌شناسی فرگشتی مانند وراثت و جهش استفاده می‌کند.
در واقع الگوریتمهای ژنتیک از اصول انتخاب طبیعی داروین برای یافتن فرمول بهینه جهت پیش‌بینی یا تطبیق الگو استفاده می‌کنند.الگوریتمهای ژنتیک اغلب گزینه خوبی برای تکنیکهای پیش‌بینی بر مبنای رگرسیون هستند. مختصراً گفته می‌شود که الگوریتم ژنتیک (یا GA) یک تکنیک برنامه‌نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مسئله استفاده می‌کند.مسئله‌ای که باید حل شود ورودی است و راه‌حلها طبق یک الگو کد گذاری می‌شوند که تابع fitness نام دارد هر راه حل کاندید را ارزیابی می‌کند که اکثر آنها به صورت تصادفی انتخاب می‌شوند.
کلاً این الگوریتم‌ها از بخش های زیر تشکیل می‌شوند : تابع برازش - نمایش – انتخاب – تغییر
هنگامی که لغت تنازع بقا به کار می‌رود اغلب بار ارزشی منفی آن به ذهن می‌آید. شاید همزمان قانون جنگل به ذهن برسد و حکم بقای قوی‌ترها!
البته همیشه هم قوی‌ترین‌ها برنده نبوده‌اند. مثلاً دایناسورها با وجود جثه عظیم و قویتر بودن در طی روندی کاملاً طبیعی بازیِ بقا و ادامه نسل را واگذار کردند در حالی که موجوداتی بسیار ضعیف‌تر از آنها حیات خویش را ادامه دادند. ظاهراً طبیعت، بهترین‌ها را تنها بر اساس هیکل انتخاب نمی‌کند! در واقع درست‌تر آنست که بگوییم طبیعت مناسب ترین‌ها (Fittest) را انتخاب می‌کند نه بهترین‌ها.
قانون انتخاب طبیعی بدین صورت است که تنها گونه‌هایی از یک جمعیت ادامه نسل می‌دهند که بهترین خصوصیات را داشته باشند و آنهایی که این خصوصیات را نداشته باشند به تدریج و در طی زمان از بین می‌روند.
مثلا فرض کنید گونه خاصی از افراد، هوش بیشتری از بقیه افرادِ یک جامعه یا کولونی دارند. در شرایط کاملاً طبیعی، این افراد پیشرفت بهتری خواهند کرد و رفاه نسبتاً بالاتری خواهند داشت و این رفاه، خود باعث طول عمر بیشتر و باروری بهتر خواهد بود (توجه کنید شرایط، طبیعیست نه در یک جامعه سطح بالا با ملاحظات امروزی؛ یعنی طول عمر بیشتر در این جامعه نمونه با زاد و ولد بیشتر همراه است). حال اگر این خصوصیت (هوش) ارثی باشد بالطبع در نسل بعدی همان جامعه تعداد افراد باهوش به دلیل زاد و ولد بیشترِ اینگونه افراد، بیشتر خواهد بود. اگر همین روند را ادامه دهید خواهید دید که در طی نسلهای متوالی دائماً جامعه نمونه ما باهوش و باهوش‌تر می‌شود. بدین ترتیب یک مکانیزم ساده طبیعی توانسته است در طی چند نسل عملاً افراد کم هوش را از جامعه حذف کند علاوه بر اینکه میزان هوش متوسط جامعه نیز دائماً در حال افزایش است.
بدین ترتیب می‌توان دید که طبیعت با بهره‌گیری از یک روش بسیار ساده (حذف تدریجی گونه‌های نامناسب و در عین حال تکثیر بالاتر گونه‌های بهینه)، توانسته است دائماً هر نسل را از لحاظ خصوصیات مختلف ارتقاء بخشد.
البته آنچه در بالا ذکر شد به تنهایی توصیف کننده آنچه واقعاً در قالب تکامل در طبیعت اتفاق می‌افتد نیست. بهینه‌سازی و تکامل تدریجی به خودی خود نمی‌تواند طبیعت را در دسترسی به بهترین نمونه‌ها یاری دهد. اجازه دهید تا این مسأله را با یک مثال شرح دهیم:
پس از اختراع اتومبیل به تدریج و در طی سال‌ها اتومبیل‌های بهتری با سرعت‌های بالاتر و قابلیت‌های بیشتر نسبت به نمونه‌های اولیه تولید شدند. طبیعیست که این نمونه‌های متأخر حاصل تلاش مهندسان طراح جهت بهینه‌سازی طراحی‌های قبلی بوده‌اند. اما دقت کنید که بهینه‌سازی یک اتومبیل، تنها یک "اتومبیل بهتر" را نتیجه می‌دهد.
اما آیا می‌توان گفت اختراع هواپیما نتیجه همین تلاش بوده است؟ یا فرضاً می‌توان گفت فضاپیماها حاصل بهینه‌سازی طرح اولیه هواپیماها بوده‌اند؟
پاسخ اینست که گرچه اختراع هواپیما قطعاً تحت تأثیر دستاورهای صنعت اتومبیل بوده است؛ اما به‌هیچ وجه نمی‌توان گفت که هواپیما صرفاً حاصل بهینه‌سازی اتومبیل و یا فضاپیما حاصل بهینه‌سازی هواپیماست. در طبیعت هم عیناً همین روند حکم‌فرماست. گونه‌های متکامل‌تری وجود دارند که نمی‌توان گفت صرفاً حاصل تکامل تدریجی گونه قبلی هستند.
در این میان آنچه شاید بتواند تا حدودی ما را در فهم این مسأله یاری کند مفهومیست به نام تصادف یا جهش.
به عبارتی طرح هواپیما نسبت به طرح اتومبیل یک جهش بود و نه یک حرکت تدریجی. در طبیعت نیز به همین گونه‌است. در هر نسل جدید بعضی از خصوصیات به صورتی کاملاً تصادفی تغییر می‌یابند سپس بر اثر تکامل تدریجی که پیشتر توضیح دادیم در صورتی که این خصوصیت تصادفی شرایط طبیعت را ارضا کند حفظ می‌شود در غیر این‌صورت به شکل اتوماتیک از چرخه طبیعت حذف میگردد.
در واقع می‌توان تکامل طبیعی را به این‌صورت خلاصه کرد: جست‌وجوی کورکورانه (تصادف یا Blind Search) + بقای قویتر.
حال ببینیم که رابطه تکامل طبیعی با روشهای هوش مصنوعی چیست. هدف اصلی روشهای هوشمندِ به کار گرفته شده در هوش مصنوعی، یافتن پاسخ بهینه مسائل مهندسی است. بعنوان مثال اینکه چگونه یک موتور را طراحی کنیم تا بهترین بازدهی را داشته باشد یا چگونه بازوهای یک ربات را متحرک کنیم تا کوتاه‌ترین مسیر را تا مقصد طی کند (دقت کنید که در صورت وجود مانع یافتن کوتاه‌ترین مسیر دیگر به سادگی کشیدن یک خط راست بین مبدأ و مقصد نیست) همگی مسائل بهینه‌سازی هستند.
روشهای کلاسیک ریاضیات دارای دو اشکال اساسی هستند. اغلب این روش‌ها نقطه بهینه محلی (Local Optima) را بعنوان نقطه بهینه کلی در نظر می‌گیرند و نیز هر یک از این روش‌ها تنها برای مسأله خاصی کاربرد دارند. این دو نکته را با مثال‌های ساده‌ای روشن می‌کنیم.
به شکل زیر توجه کنید. این منحنی دارای دو نقطه ماکزیمم می‌باشد. که یکی از آنها تنها ماکزیمم محلی است. حال اگر از روشهای بهینه‌سازی ریاضی استفاده کنیم مجبوریم تا در یک بازه بسیار کوچک مقدار ماکزیمم تابع را بیابیم. مثلاً از نقطه 1 شروع کنیم و تابع را ماکزیمم کنیم. بدیهی است اگر از نقطه 1 شروع کنیم تنها به مقدار ماکزیمم محلی دست خواهیم یافت و الگوریتم ما پس از آن متوقف خواهد شد. اما در روشهای هوشمند، به ویژه الگوریتم ژنتیک بدلیل خصلت تصادفی آنها حتی اگر هم از نقطه 1 شروع کنیم باز ممکن است در میان راه نقطه A به صورت تصادفی انتخاب شود که در این صورت ما شانس دست‌یابی به نقطه بهینه کلی (Global Optima) را خواهیم داشت.
در مورد نکته دوم باید بگوییم که روشهای ریاضی بهینه‌سازی اغلب منجر به یک فرمول یا دستورالعمل خاص برای حل هر مسئله می‌شوند. در حالی که روشهای هوشمند دستورالعمل‌هایی هستند که به صورت کلی می‌توانند در حل هر مسئله‌ای به کار گرفته شوند. این نکته را پس از آشنایی با خود الگوریتم بیشتر و بهتر خواهید دید.
الگوریتمهای ژنتیک از اصول انتخاب طبیعی داروین برای یافتن فرمول بهینه جهت پیش‌بینی یا تطبیق الگو استفاده می‌کنند. الگوریتمهای ژنتیک اغلب گزینه خوبی برای تکنیکهای پیش‌بینی بر مبنای رگرسیون هستند.
برای مثال اگر بخواهیم نوسانات قیمت نفت را با استفاده از عوامل خارجی و ارزش رگرسیون خطی ساده مدل کنیم، این فرمول را تولید خواهیم کرد : قیمت نفت در زمان t = ضریب 1 نرخ بهره در زمان t + ضریب 2 نرخ بیکاری در زمان t + ثابت 1 . سپس از یک معیار برای پیدا کردن بهترین مجموعه ضرایب و ثابت‌ها جهت مدل کردن قیمت نفت استفاده خواهیم کرد. در این روش 2 نکته اساسی وجود دارد. اول این که روش خطی است و مسئله دوم این است که ما به جای اینکه در میان "فضای پارامترها" جستجو کنیم، پارامترهای مورد استفاده را مشخص کرده‌ایم.
با استفاده از الگوریتمهای ژنتیک ما یک ابر فرمول یا طرح، تنظیم می‌کنیم که چیزی شبیه "قیمت نفت در زمان t تابعی از حداکثر 4 متغیر است" را بیان می‌کند. سپس داده‌هایی برای گروهی از متغیرهای مختلف، شاید در حدود 20 متغیر فراهم خواهیم کرد. سپس الگوریتم ژنتیک اجرا خواهد شد که بهترین تابع و متغیرها را مورد جستجو قرار می‌دهد. روش کار الگوریتم ژنتیک به طور فریبنده‌ای ساده، خیلی قابل درک و به طور قابل ملاحظه‌ای روشی است که ما معتقدیم حیوانات آنگونه تکامل یافته‌اند. هر فرمولی که از طرح داده شده بالا تبعیت کند فردی از جمعیت فرمول‌های ممکن تلقی می‌شود.
متغیرهایی که هر فرمول داده‌شده را مشخص می‌کنند به عنوان یکسری از اعداد نشان داده‌شده‌اند که معادل [دی ان ای|دی.ان.ای](DNA) آن فرد را تشکیل می‌دهند.
موتور الگوریتم ژنتیک یک جمعیت اولیه از فرمول ایجاد می‌کند. هر فرد در برابر مجموعه‌ای از داده‌های مورد آزمایش قرار می‌گیرند و مناسبترین آنها (شاید 10 درصد از مناسبترین‌ها) باقی می‌مانند؛ بقیه کنار گذاشته می‌شوند. مناسبترین افراد با هم جفتگیری (جابجایی عناصر دی ان ای) و تغییر (تغییر تصادفی عناصر دی ان ای) کرده‌اند. مشاهده می‌شود که با گذشت از میان تعداد زیادی از نسلها، الگوریتم ژنتیک به سمت ایجاد فرمول‌هایی که دقیقتر هستند، میل می‌کنند. در حالی که شبکه‌های عصبی هم غیرخطی و غیرپارامتریک هستند، جذابیت زیاد الگوریتمهای ژنتیک این است نتایج نهایی قابل ملاحظه‌ترند. فرمول نهایی برای کاربر انسانی قابل مشاهده خواهد بود، و برای ارائه سطح اطمینان نتایج می‌توان تکنیکهای آماری متعارف را بر روی این فرمول‌ها اعمال کرد. فناوری الگوریتمهای ژنتیک همواره در حال بهبود است و برای مثال با مطرح کردن معادله ویروس‌ها که در کنار فرمول‌ها و برای نقض کردن فرمول‌های ضعیف تولید می‌شوند و در نتیجه جمعیت را کلاً قویتر می‌سازند.
مختصراً گفته می‌شود که الگوریتم ژنتیک (یا GA) یک تکنیک برنامه‌نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مسئله استفاده می‌کند. مسئله‌ای که باید حل شود ورودی است و راه حلها طبق یک الگو کدگذاری می‌شوند که تابع fitness نام دارد و هر راه حل کاندید را ارزیابی می‌کند که اکثر آنها به صورت تصادفی انتخاب می‌شوند.
الگوریتم ژنتیک (GA) یک تکنیک جستجو در علم رایانه برای یافتن راه حل بهینه و مسائل جستجو است. الگوریتمهای ژنتیک یکی از انواع الگوریتمهای تکاملی‌اند که از علم زیست‌شناسی مثل وراثت، جهش، [انتخاب ناگهانی(زیست‌شناسی)|انتخاب ناگهانی]، انتخاب طبیعی و ترکیب الهام گرفته شده.
عموماً راه‌حلها به صورت 2 تایی 0 و 1 نشان داده می‌شوند، ولی روشهای نمایش دیگری هم وجود دارد. تکامل از یک مجموعه کاملاً تصادفی از موجودیت‌ها شروع می‌شود و در نسلهای بعدی تکرار می‌شود. در هر نسل، مناسبترین‌ها انتخاب می‌شوند نه بهترین‌ها.
یک راه‌حل برای مسئله مورد نظر، با یک لیست از پارامترها نشان داده می‌شود که به آنها کروموزوم یا ژنوم می‌گویند. کروموزوم‌ها عموماً به صورت یک رشته ساده از داده‌ها نمایش داده می‌شوند، البته انواع ساختمان داده‌های دیگر هم می‌توانند مورد استفاده قرار گیرند. در ابتدا چندین مشخصه به صورت تصادفی برای ایجاد نسل اول تولید می‌شوند. در طول هر نسل، هر مشخصه ارزیابی می‌شود وارزش تناسب (fitness) توسط تابع تناسب اندازه‌گیری می‌شود.
گام بعدی ایجاد دومین نسل از جامعه است که بر پایه فرآیندهای انتخاب، تولید از روی مشخصه‌های انتخاب شده با عملگرهای ژنتیکی است: اتصال کروموزوم‌ها به سر یکدیگر و تغییر.
برای هر فرد، یک جفت والد انتخاب می‌شود. انتخاب‌ها به گونه‌ای‌اند که مناسبترین عناصر انتخاب شوند تا حتی ضعیفترین عناصر هم شانس انتخاب داشته باشند تا از نزدیک شدن به جواب محلی جلوگیری شود. چندین الگوی انتخاب وجود دارد: چرخ منگنه‌دار(رولت)، انتخاب مسابقه‌ای (Tournament) ،... .
معمولاً الگوریتمهای ژنتیک یک عدد احتمال اتصال دارد که بین 0.6 و 1 است که احتمال به وجود آمدن فرزند را نشان می‌دهد. ارگانیسم‌ها با این احتمال دوباره با هم ترکیب می‌شوند. اتصال 2 کروموزوم فرزند ایجاد می‌کند، که به نسل بعدی اضافه می‌شوند. این کارها انجام می‌شوند تا این که کاندیدهای مناسبی برای جواب، در نسل بعدی پیدا شوند. مرحله بعدی تغییر دادن فرزندان جدید است. الگوریتمهای ژنتیک یک احتمال تغییر کوچک و ثابت دارند که معمولاً درجه‌ای در حدود 0.01 یا کمتر دارد. بر اساس این احتمال، کروموزوم‌های فرزند به طور تصادفی تغییر می‌کنند یا جهش می‌یابند، مخصوصاً با جهش بیتها در کروموزوم ساختمان داده‌مان.
این فرآیند باعث به وجود آمدن نسل جدیدی از کروموزوم‌هایی می‌شود، که با نسل قبلی متفاوت است. کل فرآیند برای نسل بعدی هم تکرار می‌شود، جفت‌ها برای ترکیب انتخاب می‌شوند، جمعیت نسل سوم به وجود می‌آیند و .... این فرآیند تکرار می‌شود تا این که به آخرین مرحله برسیم.
شرایط خاتمه الگوریتمهای ژنتیک عبارتند از:
قبل از این که یک الگوریتم ژنتیک برای یک مسئله اجرا شود، یک روش برای کد کردن ژنوم‌ها به زبان کامپیوتر باید به کار رود. یکی از روشهای معمول کد کردن به صورت رشته‌های باینری است: رشته‌های 0و1. یک راه حل مشابه دیگر کدکردن راه حلها در آرایه‌ای از اعداد صحیح یا اعشاری است، که دوباره هر جایگاه یک جنبه از ویژگی‌ها را نشان می‌دهد. این راه حل در مقایسه با قبلی پیچیده‌تر و مشکل‌تر است. مثلاً این روش توسط استفان کرمر، برای حدس ساختار 3 بعدی یک پروتئین موجود در آمینو اسید‌ها استفاده شد. الگوریتمهای ژنتیکی که برای آموزش شبکه‌های عصبی استفاده می‌شوند، از این روش بهره می‌گیرند.
سومین روش برای نمایش صفات در یک GA یک رشته از حروف است، که هر حرف دوباره نمایش دهنده یک خصوصیت از راه حل است.
خاصیت هر 3تای این روش‌ها این است که آنها تعریف سازنده‌ایی را که تغییرات تصادفی در آنها ایجاد می‌کنند را آسان می‌کنند: 0 را به 1 وبرعکس، اضافه یا کم کردن ارزش یک عدد یا تبدیل یک حرف به حرف دیگر.
یک روش دیگر که توسط John Koza توسعه یافت، برنامه‌نویسی ژنتیک (genetic programming)است. که برنامه‌ها را به عنوان شاخه‌های داده در ساختار درخت نشان می‌دهد. در این روش تغییرات تصادفی می‌توانند با عوض کردن عملگرها یا تغییر دادن ارزش یک گره داده شده در درخت، یا عوض کردن یک زیر درخت با دیگری به وجود آیند.
در هر مسئله قبل از آنکه بتوان الگوریتم ژنتیک را برای یافتن یک پاسخ به کار برد به دو عنصر نیاز است:در ابتدا روشی برای ارائه یک جواب به شکلی که الگوریتم ژنتیک بتواند روی آن عمل کند لازم است. در روش سنتی یک جواب به صورت یک رشته از بیتها، اعداد یا نویسهها نمایش داده می‌شود.دومین جزء اساسی الگوریتم ژنتیک روشی است که بتواند کیفیت هر جواب پیشنهاد شده را با استفاده از توابع تناسب محاسبه نماید. مثلاً اگر مسئله هر مقدار وزن ممکن را برای یک کوله پشتی مناسب بداند بدون اینکه کوله پشتی پاره شود، (مسئله کوله پشتی را ببینید) یک روش برای ارائه پاسخ می‌تواند به شکل رشته ای از بیتهای ? و? در نظر گرفته شود، که ? یا ? بودن نشانه اضافه شدن یا نشدن وزن به کوله پشتی است.تناسب پاسخ، با تعیین وزن کل برای جواب پیشنهاد شده اندازه گیری می‌شود.
1 Genetic Algorithm
2 begin 3 Choose initial population
4 repeat 5 Evaluate the individual fit nesses of a certain proportion of the population
6 Select pairs of best-ranking individuals to reproduce
7 Apply crossover operator
8 Apply mutation operator
9 until terminating condition
10 end
در دهه هفتاد میلادی دانشمندی از دانشگاه میشیگان به نام جان هلند ایده استفاده از الگوریتم ژنتیک را در بهینه‌سازی‌های مهندسی مطرح کرد. ایده اساسی این الگوریتم انتقال خصوصیات موروثی توسط ژن‌هاست. فرض کنید مجموعه خصوصیات انسان توسط کروموزوم‌های او به نسل بعدی منتقل می‌شوند. هر ژن در این کروموزوم‌ها نماینده یک خصوصیت است. بعنوان مثال ژن 1 می‌تواند رنگ چشم باشد، ژن 2 طول قد، ژن 3 رنگ مو و الی آخر. حال اگر این کروموزوم به تمامی، به نسل بعد انتقال یابد، تمامی خصوصیات نسل بعدی شبیه به خصوصیات نسل قبل خواهد بود. بدیهیست که در عمل چنین اتفاقی رخ نمی‌دهد. در واقع بصورت همزمان دو اتفاق برای کروموزوم‌ها می‌افتد. اتفاق اول جهش (Mutation) است. "جهش" به این صورت است که بعضی ژن‌ها بصورت کاملاً تصادفی تغییر می‌کنند. البته تعداد این گونه ژن‌ها بسیار کم می‌باشد اما در هر حال این تغییر تصادفی همانگونه که پیشتر دیدیم بسیار مهم است. مثلاً ژن رنگ چشم می‌تواند بصورت تصادفی باعث شود تا در نسل بعدی یک نفر دارای چشمان سبز باشد. در حالی که تمامی نسل قبل دارای چشم قهوه‌ای بوده‌اند. علاوه بر "جهش" اتفاق دیگری که می‌افتد و البته این اتفاق به تعداد بسیار بیشتری نسبت به "جهش" رخ می‌دهد چسبیدن ابتدای یک کروموزوم به انتهای یک کروموزوم دیگر است. این مسأله با نام Crossover شناخته می‌شود. این همان چیزیست که مثلاً باعث می‌شود تا فرزند تعدادی از خصوصیات پدر و تعدادی از خصوصیات مادر را با هم به ارث ببرد و از شبیه شدن تام فرزند به تنها یکی از والدین جلوگیری می‌کند.
روشهای مختلفی برای الگوریتمهای ژنتیک وجود دارند که می‌توان برای انتخاب ژنوم‌ها از آنها استفاده کرد. اما روشهای لیست شده در پایین از معمول‌ترین روش‌ها هستند.
مناسبترین عضو هر اجتماع انتخاب می‌شود.Elitist Selection
یک روش انتخاب است که در آن عنصری که عدد برازش (تناسب) بیشتری داشته باشد، انتخاب می‌شود. در واقع به نسبت عدد برازش برای هر عنصر یک احتمال تجمعی نسبت میدهیم و با این احتمال است که شانس انتخاب هر عنصر تعیین می شود.
Roulette Selection
به موازات افزایش متوسط عدد برازش جامعه، سنگینی انتخاب هم بیشتر می‌شود و جزئی‌تر. این روش وقتی کاربرد دارد که مجموعه دارای عناصری باشد که عدد برازش بزرگی دارند و فقط تفاوت‌های کوچکی آنها را از هم تفکیک می‌کند.Scaling Selection
یک زیر مجموعه از صفات یک جامعه انتخاب می‌شوند و اعضای آن مجموعه با هم رقابت می‌کنند و سرانجام فقط یک صفت از هر زیرگروه برای تولید انتخاب می‌شوند.Tournament Selection
بعضی از روشهای دیگر عبارتند از:Hierarchical Selection, Steady-State Selection, Rank Selection, Tournament Selection
نوشته شده توسط لادن در جمعه 90/1/26 و ساعت 9:38 صبح | نظرات دیگران()
.jpg)
