نوشته‌ها

مسئله فروشنده دوره‌گرد

 اگر فروشنده دوره گرد از نقطه A شروع کند و فواصل بین نقاط مشخص باشد، کوتاه‌تربن مسیر که از تمام نقاط یکبار بازدید می‌کند و به A بازمی‌گردد کدام است؟

مسئله فروشنده دوره گرد (به انگلیسی: Travelling salesman problem، به‌اختصار: TSP) مسئله‌ای مشهور است که ابتدا در سده ۱۸مسائل مربوط به آن توسط ویلیام همیلتون و توماس کرکمن مطرح شد و سپس در دهه ۱۹۳۰ شکل عمومی آن به وسیله ریاضیدانانی مثلکارل منگر از دانشگاه هاروارد و هاسلر ویتنی از دانشگاه پرینستون مورد مطالعه قرار گرفت.

شرح مسئله بدین شکل است:

تعدادی شهر داریم و هزینه رفتن مستقیم از یکی به دیگری را می‌دانیم. مطلوب است کم‌هزینه‌ترین مسیری که از یک شهر شروع شود و از تمامی شهرها دقیقاً یکبار عبور کند و به شهر شروع برگردد.

 

مسئله فروشنده دوره گرد

تعداد جواب‌های شدنی مسئله، برابر است با {\displaystyle {\frac {1}{2}}(n-1)!}{\displaystyle {\frac {1}{2}}(n-1)!} برای n>۲ که n تعداد شهرها می‌باشد. در واقع این عدد برابر است با تعداددورهای همیلتونی در یک گراف کامل با n رأس.

مسئله‌های مرتبط

مسئله فروشنده دوره گرد یا Traveling Salesman Problem (به اختصار TSP)، یکی از مسائل بسیار مهم و پرکاربرد در علوم کامپیوتر و تحقیق در عملیات است.

سه روش کلی برای کد کردن راه حل‌های مسئله TSP ارائه شده‌است که در الگوریتم‌های مختلفی قابل استفاده هستند. راه حل‌های سه گاه عبارتند از:

الف) نمایش جواب به صورت رشته گسسته جایگشتی که در الگوریتم‌های زیر قابل استفاده است: الگوریتم ژنتیک یا Genetic Algorithms (به اختصار GA) شبیه‌سازی تبرید یا Simulated Annealing (به اختصار SA) جستجوی ممنوعه یا Tabu Search (به اختصار TS) جستجوی همسایگی متغیر یا Variable Neighborhood Search (به اختصار VNS) بهینه‌سازی کلونی مورچگان یا Ant Colony Optimization (به اختصار ACO) جستجوی هارمونی یا Harmony Search (به اختصار HS) و سایر الگوریتم‌های بهینه‌سازی گسسته

ب) نمایش جواب به صورت کلیدهای تصادفی یا Random Key که در الگوریتم‌های زیر قابل استفاده است: الگوریتم ژنتیک یا Genetic Algorithms (به اختصار GA) بهینه‌سازی ازدحام ذرات یا Particle Swarm Optimization (به اختصار PSO) الگوریتم رقابت استعماری یا Imperialist Competitive Algorithm (به اختصار ICA) تکامل تفاضلی یا Differential Evolution (به اختصار DE) بهینه‌سازی مبتنی بر جغرافیای زیستی یا Bio-geography Based Optimization (به اختصار BBO) استراتژی‌های تکاملی یا Evolution Strategies (به اختصار ES) برنامه‌ریزی تکاملی یا Evolutionary Programming (به اختصار EP) و سایر الگوریتم‌های بهینه‌سازی پیوسته

پ) نمایش جواب به شکل ماتریس‌های شبیه فرومون که توسط تمامی الگوریتم‌های اشاره شده در مورد (ب) قابل استفاده می‌باشد.

  • مسئله معادل در نظریه گراف به این صورت است که یک گراف وزن‌دار کامل داریم که می‌خواهیم کم‌وزن‌ترین دور همیلتونی را پیدا کنیم.
  • مسئله تنگراه فروشنده دوره‌گرد (به انگلیسی: Bottleneck traveling salesman problem، به‌اختصار: bottleneck TSP) مسئله‌ای بسیار کاربردی است که در یک گراف وزن‌دار کم‌وزن‌ترین دور همیلتونی را می‌خواهد که شامل سنگین‌ترین یال باشد.
  • تعمیم‌یافته مسئله فروشنده دوره‌گرد دارای ایالت‌هایی است که هر کدام حداقل یک شهر دارند و فروشنده باید از هر ایالت دقیقاً از یک شهر عبور کند. این مسئله به «مسئله سیاست‌مدار مسافر» نیز شهرت دارد.

الگوریتم‌ها

مسئله فروشنده دوره گرد جزء مسائل ان‌پی سخت است. راه‌های معمول مقابله با چنین مسائلی عبارتند از:

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

الگوریتم‌های دقیق

سرراست‌ترین راه حل امتحان کردن تمامی جایگشتهای ممکن برای پیدا کردن ارزان‌ترین مسیر است که چون تعداد جایگشت‌ها !n است، این راه حل غیرعملی می‌شود. با استفاده از برنامه‌نویسی پویا مسئله می‌تواند با مرتبه زمانی{\displaystyle n^{2}2^{n}}{\displaystyle n^{2}2^{n}} حل شود. راه‌های دیگر استفاده از الگوریتم‌های انشعاب و تحدید برای ۴۰ تا ۶۰ شهر، استفاده از برنامه‌نویسی خطی برای کوچکتر از ۲۰۰ شهر و استفاده از روش برش-صفحه برای اندازه‌های بزرگ است.

الگوریتم‌های مکاشفه‌ای

الگوریتم‌های تقریبی متنوعی وجود دارند که خیلی سریع جواب‌های درست را با احتمال بالا به‌دست می‌دهند که می‌توان آن‌ها را به صورت زیر دسته‌بندی کرد:

  • مکاشفه‌ای سازنده
  • بهبود تکراری
    • مبادله دوبه‌دو
    • مکاشفه‌ای k-opt
    • مکاشفه‌ای V-opt
  • بهبود تصادفی

پیچیدگی محاسباتی الگوریتم فروشنده دوره گرد

این الگوریتم بطور مستقیم در مرتبه زمانی(!O(n حل می‌شود اما اگر به روش برنامه‌نویسی پویا برای حل آن استفاده کنیم مرتبه زمانی آن (O(n^2*2^n خواهد شد که جز مرتبه‌های نمایی است. باید توجه داشت علی‌رغم آنکه مرتبه نمایی مذکور زمان بسیار بدی است اما همچنان بسیار بهتر از مرتبه فاکتوریل می‌باشد. شبه کد الگوریتم فوق به صورت زیر است که در آن تعداد زیر مجموعه‌های یک مجموعه n عضوی ۲ به توان n می‌باشد و for اول یک ضریب n را نیز حاصل می‌شود که به ازای تمام شهرهای غیر مبدأ می‌باشد و حاصل (n*(2^n را پدیدمی‌آورد؛ بنابراین برای جستجوی کمترین مقدار نیاز به یک عملیات خطی از مرتبه n داریم که در زمان فوق نیز ضرب می‌شود و در نهایت زمان (n^2)*(2^n) را برای این الگوریتم حاصل می‌کند.

 

C({1},1) = 0
  for (S=2 to n)
  for All Subsets S subset of {1,2,3,...} of size S and containing1
  C(S,1) = &
  for All J member of S , J<>1
  C (S , J) = min { C (S - { J } , i) + D i,J: i member of S , i <> J }
 return min j C ({1 . . . n}, J) + D J,1

 

شبه کد مسئله فروشنده دوره گرد

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

ورودی:یک گراف وزن دار و جهت دار و n تعداد گره‌های گراف. گراف با یک ارائه دو بعدی w مشخص می‌شود که سطرها و ستون‌هایش از ۱ تا n شاخص دهی شده‌اند و در ان [w[i][j معرف وزن لبه از گره iام به گره jام است.۴

خروجی:یک متغیر minlength که مقدار ان طول تور بهینه است و یک ارائه دو بعدی p که یک تور بهینه را از روی ان می‌توان ساخت . سطرهای p از ۱ تا n و ستونهای ان با تمامی زیر مجموعه‌های {v-{v1 شاخص دهی شده‌اند . [P[i][A شاخص اولین گره بعد از vi بر روی کوتاهترین مسیر از viتاvj است که از تمام گره‌های A دقیقاً یکبار می‌گذرد.

 

* Void travel ( int n ,
 *              const number W[][],
 * index p[][],
 * number&minlength
* )
* {
* Index i, j, k;
* number D[1..n][subset of V-{vi}];
* for (i= 2 ; i<=n;i++)
* D[i][∅} = w[i][1];
* for(k=1; k<=n-2 ; k++)
* for (all subsets A v-{v1} containing k vertices
* for (i such that j≠۱ and vi is not in A){
* D[i][A] = minimum (W[i][j]+ D[vj][A-{vj}]);
* P[i][A]= value of j that gave the minimum
* }
* D[1][v-{vi}]= minimum (W[1][j]+ D[vj][V-{v1}];
* P[1][V-{v1}]= value of j that gave the minimum ;
* Minlength = D[1][V-{v1}];
* }

 

الگوریتم جستجوی ممنوعه یا Tabu Search یا به اختصار TS، یکی از قوی‌ترین الگوریتم‌ها در زمینه حل مسائل بهینه‌سازی، به خصوص مسائل بهینه‌سازی مبتنی بر گراف و مسائل بهینه‌سازی ترکیباتی (Combinatorial Optimization) است. این الگوریتم در اواخر دهه ۱۹۸۰ و توسط گلووِر (Glover) و همکارانش ارائه گردید. غالباً یکی از مسائلی که برای حل آن‌ها از الگوریتم TS استفاده می‌شود، مسئله فروشنده دوره گرد یا TSP است. این الگوریتم پاسخ‌های بسیار مناسبی را برای انواع مسائل گسسته به خصوص مسئله TSP ارائه می‌کند!

منبع


 

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

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

 

به صورت کلی مسئله فروشنده دوره گرد دارای ۳ حالت زیر می باشد.

۱-    فروشنده دوره گرد متقارن

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

۲-   فروشنده دوره گرد نامتقارن

مسأله ­ي فروشنده ­ي دوره­ گرد نامتقارن, یک TSP است که فاصله بين رئوس آن, متقارن نيست. ATSP بسيار مشکل­تر از TSP است، در حقيقت در حالي که TSP متقارن, حتي در گراف­هاي با چندين هزار  رأس, به طور بهينه, قابل حل است, تنها نمونه­هاي خاصي ازATSP را که ماتريس فاصله­ي آنها, تقريباً متقارن است, تنها در گراف­هاي داراي چندين دوجين رأس, مي­توان به طور بهينه حل کرد. به کاربردن هوش مصنوعی  براي ATSP, راحت­ و سر راست است. چون هيچ تغييراتي در الگوريتم اصلي, لازم ندارد. پيچيدگي محاسباتي در حلقه­ي الگوريتم, برنامه­ي کاربردي TSP, يکسان است, زيرا تنها تفاوت آنها در فاصله­ها و ماتريس­هاي ردپا است که در اينجا ديگر متقارن نيستند.

۳-   فروشنده دوره گرد با پنجره های زمانی

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

منبع : http://travelling-salesman.blogfa.com

 

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

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

مقدمه

هنگامی که لغت تنازع بقا به کار می‌رود اغلب بار ارزشی منفی آن به ذهن می‌آید. شاید همزمان قانون جنگل به ذهن برسد و حکم بقای قوی‌ترها!

البته همیشه هم قوی‌ترین‌ها برنده نبوده‌اند. مثلاً دایناسورها با وجود جثه عظیم و قوی‌تر بودن در طی روندی کاملاً طبیعی بازیِ بقا و ادامه نسل را واگذار کردند در حالی که موجوداتی بسیار ضعیف‌تر از آنها حیات خویش را ادامه دادند. ظاهراً طبیعت، بهترین‌ها را تنها بر اساس هیکل انتخاب نمی‌کند! در واقع درست‌تر آنست که بگوییم طبیعت مناسب ترین‌ها (Fittest) را انتخاب می‌کند نه بهترین‌ها.

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

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

الف) معرفی جواب‌های مسئله به عنوان کروموزوم

ب) معرفی تابع برازندگی (فیت نس)

ج) جمع‌آوری اولین جمعیت

د) معرفی عملگرهای انتخاب

ه) معرفی عملگرهای تولید مثل

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

مثلاً فرض کنید گونه خاصی از افراد، هوش بیشتری از بقیه افرادِ یک جامعه یا کولونی دارند. در شرایط کاملاً طبیعی، این افراد پیشرفت بهتری خواهند کرد و رفاه نسبتاً بالاتری خواهند داشت و این رفاه، خود باعث طول عمر بیشتر و باروری بهتر خواهد بود (توجه کنید شرایط، طبیعیست نه در یک جامعه سطح بالا با ملاحظات امروزی؛ یعنی طول عمر بیشتر در این جامعه نمونه با زاد و ولد بیشتر همراه است). حال اگر این خصوصیت (هوش) ارثی باشد بالطبع در نسل بعدی همان جامعه تعداد افراد باهوش به دلیل زاد و ولد بیشترِ این‌گونه افراد، بیشتر خواهد بود. اگر همین روند را ادامه دهید خواهید دید که در طی نسل‌های متوالی دائماً جامعه نمونه ما باهوش و باهوش‌تر می‌شود. بدین ترتیب یک مکانیزم ساده طبیعی توانسته‌است در طی چند نسل عملاً افراد کم هوش را از جامعه حذف کند علاوه بر اینکه میزان هوش متوسط جامعه نیز دائماً در حال افزایش است.

بدین ترتیب می‌توان دید که طبیعت با بهره‌گیری از یک روش بسیار ساده (حذف تدریجی گونه‌های نامناسب و در عین حال تکثیر بالاتر گونه‌های بهینه)، توانسته‌است دائماً هر نسل را از لحاظ خصوصیات مختلف ارتقاء بخشد.

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

پس از اختراع اتومبیل به تدریج و در طی سال‌ها اتومبیل‌های بهتری با سرعت‌های بالاتر و قابلیت‌های بیشتر نسبت به نمونه‌های اولیه تولید شدند. طبیعیست که این نمونه‌های متأخر حاصل تلاش مهندسان طراح جهت بهینه‌سازی طراحی‌های قبلی بوده‌اند. اما دقت کنید که بهینه‌سازی یک اتومبیل، تنها یک «اتومبیل بهتر» را نتیجه می‌دهد.

اما آیا می‌توان گفت اختراع هواپیما نتیجه همین تلاش بوده‌است؟ یا فرضاً می‌توان گفت فضاپیماها حاصل بهینه‌سازی طرح اولیه هواپیماها بوده‌اند؟

پاسخ اینست که گرچه اختراع هواپیما قطعاً تحت تأثیر دستاوردهای‌های صنعت اتومبیل بوده‌است؛ اما به هیچ وجه نمی‌توان گفت که هواپیما صرفاً حاصل بهینه‌سازی اتومبیل یا فضاپیما حاصل بهینه‌سازی هواپیماست. در طبیعت هم عیناً همین روند حکم‌فرماست. گونه‌های متکامل‌تری وجود دارند که نمی‌توان گفت صرفاً حاصل تکامل تدریجی گونه قبلی هستند.

در این میان آنچه شاید بتواند تا حدودی ما را در فهم این مسئله یاری کند مفهومیست به نام تصادف یا جهش.

به عبارتی طرح هواپیما نسبت به طرح اتومبیل یک جهش بود و نه یک حرکت تدریجی. در طبیعت نیز به همین گونه‌است. در هر نسل جدید بعضی از خصوصیات به صورتی کاملاً تصادفی تغییر می‌یابند سپس بر اثر تکامل تدریجی که پیشتر توضیح دادیم در صورتی که این خصوصیت تصادفی شرایط طبیعت را ارضا کند حفظ می‌شود در غیر این‌صورت به شکل اتوماتیک از چرخه طبیعت حذف می‌گردد.

در واقع می‌توان تکامل طبیعی را به این‌صورت خلاصه کرد: جستجوی کورکورانه (تصادف یا Blind Search) + بقای قوی‌تر.

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

روش‌های کلاسیک ریاضیات دارای دو اشکال اساسی هستند. اغلب این روش‌ها نقطه بهینه محلی (Local Optima) را بعنوان نقطه بهینه کلی در نظر می‌گیرند و نیز هر یک از این روش‌ها تنها برای مسئله خاصی کاربرد دارند. این دو نکته را با مثال‌های ساده‌ای روشن می‌کنیم.

به شکل زیر توجه کنید. این منحنی دارای دو نقطه ماکزیمم می‌باشد؛ که یکی از آنها تنها ماکزیمم محلی است. حال اگر از روش‌های بهینه‌سازی ریاضی استفاده کنیم مجبوریم تا در یک بازه بسیار کوچک مقدار ماکزیمم تابع را بیابیم. مثلاً از نقطه ۱ شروع کنیم و تابع را ماکزیمم کنیم. بدیهی است اگر از نقطه ۱ شروع کنیم تنها به مقدار ماکزیمم محلی دست خواهیم یافت و الگوریتم ما پس از آن متوقف خواهد شد. اما در روش‌های هوشمند، به ویژه الگوریتم ژنتیک به دلیل خصلت تصادفی آنها حتی اگر هم از نقطه ۱ شروع کنیم باز ممکن است در میان راه نقطه A به صورت تصادفی انتخاب شود که در این صورت ما شانس دست‌یابی به نقطه بهینه کلی (Global Optima) را خواهیم داشت.

بهینه محلی و بهینه کلی

 

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

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

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

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

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

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

معمولاً الگوریتم‌های ژنتیک یک عدد احتمال اتصال دارد که بین ۰٫۶ و ۱ است که احتمال به وجود آمدن فرزند را نشان می‌دهد. ارگانیسم‌ها با این احتمال دوباره با هم ترکیب می‌شوند. اتصال ۲ کروموزوم فرزند ایجاد می‌کند، که به نسل بعدی اضافه می‌شوند. این کارها انجام می‌شوند تا این که کاندیدهای مناسبی برای جواب، در نسل بعدی پیدا شوند. مرحله بعدی تغییر دادن فرزندان جدید است. الگوریتم‌های ژنتیک یک احتمال تغییر کوچک و ثابت دارند که معمولاً درجه‌ای در حدود ۰٫۰۱ یا کمتر دارد. بر اساس این احتمال، کروموزوم‌های فرزند به طور تصادفی تغییر می‌کنند یا جهش می‌یابند، مخصوصاً با جهش بیت‌ها در کروموزوم ساختمان داده‌مان.

این فرایند باعث به وجود آمدن نسل جدیدی از کروموزوم‌هایی می‌شود، که با نسل قبلی متفاوت است. کل فرایند برای نسل بعدی هم تکرار می‌شود، جفت‌ها برای ترکیب انتخاب می‌شوند، جمعیت نسل سوم به وجود می‌آیند و … این فرایند تکرار می‌شود تا این که به آخرین مرحله برسیم.

شرایط خاتمه الگوریتم‌های ژنتیک عبارتند از:

  • به تعداد ثابتی از نسل‌ها برسیم.
  • بودجه اختصاص داده‌شده تمام شود (زمان محاسبه/پول).
  • یک فرد (فرزند تولید شده) پیدا شود که مینیمم (کمترین) ملاک را برآورده کند.
  • بیشترین درجه برازش فرزندان حاصل شود یا دیگر نتایج بهتری حاصل نشود.
  • بازرسی دستی.
  • ترکیبهای بالا.

روش‌های نمایش

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

خاصیت هر سه روش این است که آنها تعریف سازنده‌ای را که تغییرات تصادفی در آنها ایجاد می‌کنند را آسان می‌کنند: ۰ را به ۱ و برعکس، اضافه یا کم کردن ارزش یک عدد یا تبدیل یک به صفر یا برعکس. یک روش دیگر که توسط John Koza توسعه یافت، برنامه‌نویسی ژنتیک است؛ که برنامه‌ها را به عنوان شاخه‌های داده در ساختار درخت نشان می‌دهد. در این روش تغییرات تصادفی می‌توانند با عوض کردن عملگرها یا تغییر دادن ارزش یک گره داده شده در درخت، یا عوض کردن یک زیر درخت با دیگری به وجود آیند.

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

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

شبه کد

 ۱ Genetic Algorithm
 ۲ begin
 ۳ Choose initial population
 ۴ repeat
 ۵ Evaluate the individual fitness of a certain proportion of the population
 ۶ Select pairs of best-ranking individuals to reproduce
 ۷ Apply crossover operator
 ۸ Apply mutation operator
 ۹ until terminating condition
۱۰ end

شمای کلی شبه کد شمای کلی شبه کد

 

ایده اصلی

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

«جهش» به این صورت است که بعضی ژن‌ها بصورت کاملاً تصادفی تغییر می‌کنند. البته تعداد این‌گونه ژن‌ها بسیار کم می‌باشد اما در هر حال این تغییر تصادفی همانگونه که پیشتر دیدیم بسیار مهم است. مثلاً ژن رنگ چشم می‌تواند بصورت تصادفی باعث شود تا در نسل بعدی یک نفر دارای چشمان سبز باشد. در حالی که تمامی نسل قبل دارای چشم قهوه‌ای بوده‌اند. علاوه بر «جهش» اتفاق دیگری که می‌افتد و البته این اتفاق به تعداد بسیار بیشتری نسبت به «جهش» رخ می‌دهد چسبیدن دو کروموزوم از طول به یکدیگر و تبادل برخی قطعات بین دو کروموزوم است. این مسئله با نام Crossover شناخته می‌شود. این همان چیزیست که باعث می‌شود تا فرزندان ترکیب ژنهای متفاوتی را (نسبت به والدین خود) به فرزندان خود انتقال دهند.

روش‌های انتخاب

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

انتخاب Elitist

مناسب‌ترین عضو هر اجتماع انتخاب می‌شود.

انتخاب Roulette

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

انتخاب Scaling

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

انتخاب Tournament

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

بعضی از روش‌های دیگر عبارتند از:

  • Hierarchical Selection
  • Steady-State Selection
  • Rank Selection

مثال عملی

در این مثال می‌خواهیم مسئلهٔ ۸ وزیر را بوسیلهٔ این الگوریتم حل کنیم. هدف مشخص کردن چیدمانی از ۸ وزیر در صفحهٔ شطرنج است به نحوی که هیچ‌یک همدیگر را تهدید نکند. ابتدا باید نسل اولیه را تولید کنیم. صفحه شطرنج ۸ در ۸ را در نظر بگیرید. ستونها را با اعداد ۰ تا ۷ و سطرها را هم از ۰ تا ۷ مشخص می‌کنیم. برای تولید حالات (کروموزومها) اولیه بصورت تصادفی وزیرها را در ستونهای مختلف قرار می‌دهیم. باید در نظر داشت که وجود نسل اولیه با شرایط بهتر سرعت رسیدن به جواب را افزایش می‌دهد (اصالت نژاد) به همین خاطر وزیر i ام را در خانهٔ تصادفی در ستون i ام قرار می‌دهیم (به جای اینکه هر مهره‌ای بتواند در هر خانه خالی قرار بگیرد). با اینکار حداقل از برخورد ستونی وزیرها جلوگیری می‌شود.

توضیح بیشتر اینکه مثلاً وزیر اول را بطور تصادفی درخانه‌های ستون اول که با ۰ مشخص شده قرار می‌دهیم تا به آخر. i=۰٬۱، … ۷ حال باید این حالت را به نحوی کمی مدل کرد. چون در هر ستون یک وزیر قرار دادیم هر حالت را بوسیلهٔ رشته اعدادی که عدد k ام در این رشته شمارهٔ سطر وزیر موجود در ستون i ام را نشان می‌دهد. یعنی یک حالت که انتخاب کردیم می‌تواند بصورت زیر باشد: ۶۷۲۰۳۴۲۲ که ۶ شمارهٔ سطر ۶ است که وزیر اول که شمارهٔ ستونش ۰ است می‌باشد تا آخر. فرض کنید ۴ حالت زیر به تصادف تولید شده‌اند. این چهار حالت را بعنوان کروموزومهای اولیه بکار می‌گیریم.

  1. ) ۶۷۲۰۳۴۲۰
  2. ) ۷۰۰۶۳۳۵۴
  3. ) ۱۷۵۲۲۰۶۳
  4. )۴۳۶۰۲۴۷۱

حال نوبت به تابع برازش fitness function می‌رسد. تابعی را که در نظر می‌گیریم تابعی است که برای هر حالت تعداد برخوردها (تهدیدها) را در نظر می‌گیرد. هدف صفر کردن یا حداقل کردن این تابع است. پس احتمال انتخاب کروموزومی برای تولید نسل بیشتر است که مقدار محاسبه شده توسط تابع برازش برای آن کمتر باشد. (روشهای دیگری نیز برای انتخاب وجود دارد) مقدار برازش برای حالات اولیه بصورت زیر می‌باشد: (مقدار عدد برازش در جلوی هر کروموزوم (با رنگ قرمز)همان تعداد برخوردهای وزیران می‌باشد)

  1. )۶۷۲۰۳۴۲۰ ← ۶
  2. )۷۰۰۶۳۳۵۴ ← ۸
  3. )۱۷۵۲۲۰۶۳ ← ۲
  4. )۴۳۶۰۲۴۷۱ ← ۴

پس احتمالها بصورت زیر است:

{\displaystyle p(3)>p(4)>p(1)>p(2)}

در اینجا کروموزومهایی را انتخاب می‌کنیم که برازندگی کمتری دارند. پس کروموزوم ۳ برای crossover با کروموزومهای ۴ و ۱ انتخاب می‌شود. نقطهٔ ترکیب را بین ارقام ۶ و ۷ در نظر می‌گیریم.

۴ و ۳:

  1. )۱۷۵۲۲۰۷۱
  2. )۴۳۶۰۲۴۶۳

۱ و ۳:

  1. )۱۷۵۲۲۰۲۰
  2. )۶۷۲۰۳۴۶۳

حال نوبت به جهش می‌رسد. در جهش باید یکی از ژن‌ها تغییر کند.

فرض کنید از بین کروموزومهای ۵ تا ۸ کروموزوم شمارهٔ ۷ و از بین ژن چهارم از ۲ به ۳ جهش یابد. پس نسل ما شامل کروموزومهای زیر با امتیازات نشان داده شده می‌باشد: (امتیازات تعداد برخوردها می‌باشد)

  1. )۶۷۲۰۳۴۲۰ ← ۶
  2. )۷۰۰۶۳۳۵۴ ← ۸
  3. )۱۷۵۲۲۰۶۳ ← ۲
  4. )۴۳۶۰۲۴۷۱ ← ۴
  5. )۱۷۵۲۲۰۷۱ ← ۶
  6. )۴۳۶۰۲۴۶۳ ← ۴
  7. )۱۷۵۳۲۰۲۰ ← ۴
  8. )۶۷۲۰۳۴۶۳ ← ۵

کروموزوم ۳ کاندیدای خوبی برای ترکیب با ۶ و ۷ می‌باشد. (فرض در این مرحله جهشی صورت نگیرد و نقطهٔ اتصال بین ژنهای ۱ و ۲ باشد)

  1. )۶۷۲۰۳۴۲۰ ← ۶
  2. )۷۰۰۶۳۳۵۴ ← ۸
  3. )۱۷۵۲۲۰۶۳ ← ۲
  4. )۴۳۶۰۲۴۷۱ ← ۴
  5. )۱۷۵۲۲۰۷۱ ← ۶
  6. )۴۳۶۰۲۴۶۳ ← ۴
  7. )۱۷۵۳۲۰۳۰ ← ۴
  8. )۶۷۲۰۳۴۶۳ ← ۵
  9. )۱۳۶۰۲۴۶۳ ← ۲
  10. )۴۷۵۲۲۰۶۳ ← ۲
  11. )۱۷۵۲۲۰۲۰ ← ۴
  12. )۱۷۵۲۲۰۶۳ ← ۲

کروموزومهای از ۹ تا ۱۲ را نسل جدید می‌گوییم. بطور مشخص کروموزوم‌های تولید شده در نسل جدید به جواب مسئله نزدیکتر شده‌اند. با ادامهٔ همین روند پس از چند مرحله به جواب مورد نظر خواهیم رسید.

نحوهٔ اجرای الگوریتم ژنتیکی

الگوریتم ژنتیک قسمت ۱
الگوریتم ژنتیک قسمت ۲

تعریف

به عنوان یکی از شاخه‌های وسیع و پرکاربرد هوش مصنوعی، یادگیری ماشین (Machine learning) به تنظیم و اکتشاف شیوه‌ها و الگوریتم‌هایی می‌پردازد که بر اساس آنها رایانه‌ها و سامانه‌ها توانایی تعلٌم و یادگیری پیدا می‌کنند.

Machine Learning

اهداف و انگیزه‌ها

هدف یادگیری ماشین این است که کامپیوتر (در کلی‌ترین مفهوم آن) بتواند به تدریج و با افزایش داده‌ها کارایی بهتری در انجام وظیفهٔ مورد نظر پیدا کند. گسترهٔ این وظیفه می‌تواند از تشخیص خودکار چهره با دیدن چند نمونه از چهرهٔ مورد نظر تا فراگیری شیوهٔ گام‌برداری روبات‌های دوپا با دریافت سیگنال پاداش و تنبیه باشد.

طیف پژوهش‌هایی که در یادگیری ماشینی می‌شود گسترده‌است. در سوی نظری‌ی آن پژوهش‌گران بر آن‌اند که روش‌های یادگیری تازه‌ای به وجود بیاورند و امکان‌پذیری و کیفیت یادگیری را برای روش‌های‌شان مطالعه کنند و در سوی دیگر عده‌ای از پژوهش‌گران سعی می‌کنند روش‌های یادگیری ماشینی را بر مسایل تازه‌ای اعمال کنند. البته این طیف گسسته نیست و پژوهش‌های انجام‌شده دارای مولفه‌هایی از هر دو روی‌کرد هستند.

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

تقسیم‌بندی مسایل

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

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

اولین کاری که می‌خواهید بکنید این است که اگر ربات شما را دید خرناسه بکشد اما اگر غریبه‌ای را مشاهده کرد با صدای بلند عوعو کند. فعلاً فرض می‌کنیم که ربات توانایی تولید آن صداها را دارد اما هنوز چهرهٔ شما را یادنگرفته‌است. پس کاری که می‌کنید این است که جلوی چشم‌های‌اش قرار می‌گیرید و به کمک کنترل از راه دورتان به او دستور می‌دهید که چهره‌ای که جلوی‌اش می‌بیند را با خرناسه‌کشیدن مربوط کند.

این‌کار را برای چند زاویهٔ مختلف از صورت‌تان انجام می‌دهید تا مطمئن باشید که ربات در صورتی که شما را از مثلاً نیم‌رخ ببیند بهتان عوعو نکند. هم‌چنین شما چند چهرهٔ غریبه نیز به او نشان می‌دهید و چهرهٔ غریبه را با دستور عوعوکردن مشخص می‌کنید. در این حالت شما به کامپیوتر ربات گفته‌اید که چه ورودی را به چه خروجی مربوط کند. دقت کنید که هم ورودی و هم خروجی مشخص است و در اصطلاح خروجی برچسب‌دار است. به این شیوهٔ یادگیری، یادگیری بانظارت می‌گویند.

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

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

یادگیری بی‌نظارت را می‌توان به صورت عمل کاهش بعد در نظر گرفت.

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

یادگیری با نظارت

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

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

تعریف ریاضی مسایل یادگیری ماشین

یادگیری با نظارت

در این مدل یادگیری مثال‌های آموزشی به صورت جفت‌های (x^{i},y^{i}) که در آن هر نمونه به همراه بر چسب آن داده شده‌اند و i اندیس هر مثال در مجموعه مثال‌های آموزشی D است. هدف در این یادگیری بدست آوردن تابع f است که بتواند برای نمونه‌های ورودی دیده نشده x بر چسب مناسب را برگرداند(f(x) = y). نمونه و بر چسب هر دو می‌توانند یک بردار باشند. اگر بر چسب یک عدد حقیقی باشد مسئله پیش روی ما رگرسیون نامیده می‌شود. اگر بر چسب یک عدد صحیح باشد به مسئله دستبه بندی گفته می‌شود.

 

یکی از انواع یادگیری از داده‌ها

منبع


یادگیری ماشین قسمت ۱
یادگیری ماشین قسمت ۲
یادگیری ماشین قسمت ۳

چکیده

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

کلمات کلیدی: ارتقای تصاویر رنگی ، قطعه بندی تصاویر رنگی ، رویکردهای غیر کلاسیک، رویکرهای غیر کلاسیک

مقدمه

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

نسبت ها ی محاسباتی وابسته به اجزای رنگها ، همبستگی ورودی و نمایش مشخصه های غیر خطی می باشد.

گام اصلی در پردازش تصاویر دیجیتالی ۱-پیش پردازش داده ها برای آماده سازی داده ها برای ارتقای کنتراست ، کاهش نویز و یا فیلترینگ است. ۲- استخراج ویژگیها برای بازیابی اطلاعات غیر زائد و با ارزش از یک تصویر.

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

به طور کلی مشخصه ها و بهینه سازی های یک الگوریتم توسط دامنه ای از داده های ورودی که قابلیت پردازش را دارند معین می شوند. دامنه داده معمولی شامل پیکسل ها، ویژگیهای محلی و لبه های تصاویر، اشیاء ادغام شدنی و مقدار ناچیزی از نامها می شوند.

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

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

به طور پیش فرض چند اندازه برای نمایش حالتها انتخاب می کنند مانند E که برای نمایش آنتروپی استفاده می شود. اندازه های مفید تجربی برای انعکاس قابلیت های قطعه بندی استفاده می شوند. اندازه های با مقادیر پائین قابلیت های بهتری از قطعه بندی را بدست می آورند.

رویکردهای کلاسیک در قطعه بندی و پردازش تصاویر رنگی

تکنیک های فیلترینگ برای حذف نویز و ارتقا لبه ها در سالهای اخیر به یک مسئله مهم و معروف تبدیل شده است. فلیتر بردار جهت دار (VDF) با در نظر گرفتن مقادیر سیگنال نقش مهمی در پردازش تصاویر عهده دار است. پردازش اندازه و جهت سیگنال در این کلاس از فیلتر های مستقل انجام می شود. فیلتر های چندگانه ارتقا لبه بر اساس بردار میانگین برای ارتقاء لبه های خفیف در تصاویر رنگی ارائه کردند. در این روش از سه زیر فیلتر (sub filter) استفاده می شود و سر انجام خروجی این زیر فیلتر ها با بردار میانگین مقایسه می شودو یک روش دیگر با توجه به نویز برای اطلاعات چندگانه فیلتر های نزدیکترین  همسایگی سازگار است. این فیلتر از ضرائب اطلاعات مستقل براساس یک روش اندازه گیری فاصله جدید که شامل بردار هاوی (جهت) فیلتر واندازه بردار فیلتر می باشد بهره می برد.

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

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

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

رویکردها دیگر از پردازش و قطعه بندی تصاویر رنگی

بیشتر رویکردهای کلاسیک نیاز به دانش اولیه از داده ها ی تصویر برای پردازش تصویر و قطعه بندی آن و توزیع شدت های رنگ  اصلی و پارامترهای عملیاتی تصاویر دارند. در رویکردهای غیر کلاسیک که شامل  عصبی ،فازی، ژنتیک و wavelet می شوند نیازی به توزیع ها و پارمترهای عملیاتی ندارند. در این قسمت انواع این روشها را شرح می دهیم:

الف- روش های مبتنی بر شبکه های عصبی

در این روش از ساختار شبکه ی عصبی چند سطحی CNN برای پردازش تصاویر رنگی در مدل های رنگی RGB استفاده می شود. در این روش رنگ های اولیه یک سطح منحصر به فرد CNN می باشد که برای پردازش موازی بکار می رود. اخیرا ساختار CNN چند سطحی بر ای تصاویر رنگی در حال بررسی و استفاده می باشد.

از یادگیری رقابتی CL برای خوشه های رنگی مبتنی بر کمترین مجموع مربعات معیارها بکار گیری می شود.

Clهمگن  محلی برای خوشه بندی رنگی بهینه است. در مقایسه کارایی CLبا الگوریتم های خوشه بندی موجود شبیه CMA ,GCMA ,HCL می توان گفت که دو  روش GCMA ,HCL در مقابل شرط ابتدایی حساسیتی را از خود نشان نمی دهند نتایج GCMA اکثر مواقع بهینه است ولی دارای هزینه محاسباتی بالایی می باشد در مقابل HCL دارای هزینه محاسباتی کم می باشد ولی بهینه نیست. در نتیجه در خوشه بندی سریع از CL برای خوشه بندی داده ها استفاده می شود.

Som در بسیاری از موارد استفاده می شود در دامنه نظر به اینکه می تواند بازیابی کند محتوای رنگی برجسته را از تصاویر . به طور کلی از چندین شبکه som برای خوشه بندی مبتنی بر رنگ و ویژگیهای فضایی از پیکسل های تصاویر استفاده می شود. خروجی خوشه بندی، یک رویه مطلوب از قطعه بندی تصویر است.  Som تولید کرد نتایج خوشه بندی اولیه را مبتنی بر آموزش مجموعه ها از بردار ۵ بعدی (R,G,B,x,y). تصاویر قطعاتی که توسط الحاق بلوکهای پراکنده و حذف پیکسل های ایزوله شده بوجود آمده اند. در یک مدل چند سطحی سازماندهی شبکه های عصبی (PSONN) بهینه است در استخراج رنگ های اشیاء از نویزهای رنگی تصاویر. بکارگیری معماری (PSONN) برای قطعه بندی رنگ ها  حقیقی تصاویر استفاده می شوند برای  چندین سطح از تابع های فعال سازی  مشخصه های تصاویر  توسط پارامترهای آستانه گیری ثابت و یکسان .

ب- رویکرد های مبتنی بر منطق فازی

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

الگوریتم  قطعه بندی تصاویر تکرار شونده در منطق فازی توسعه پیدا کرد . فضای رنگی  HSV مبتنی بر رویکرد فازی برای شناسایی رنگ ها اشیا در پشت زمینه های پیچیده بکارگیری شد که شامل روشنایی های متفاوت  می با شد. یک رویکرد دینامیکی فازی مبتنی بر خواص پیکسا های تصویر وجود دارد. توطعه پیدا کرد شبکه عصبی min-max بر پایه تکنیک های قعه بندی تصاویر (FMMSIS) برای کشف تصاویر مصنوعی. روش ارائه شده برای پیدا کردن مرزهای مینیمم مربعی (MBR) برای نمایش اشیاء در تصاویر بکار می رود.برچسب عصب فازی یک نمونه قابل توجیه مبتنی بر بردار تدریجی، الگوریتم  عصب گازی در جهت نماهای خوشه بندی است.

سیستم های فازی عصبی مبتنی بر یک نوع جدید از شبکه های عصبی مصنوعی هستند که  شبکه عصبی افزاینده وزن دار نامیده می شود (WINN). این سیستم ها  در سه گام عمل میکند: در ابتدا مجموعه داده های ورودی وزن دهی می شوند در شبکه . انعکاس پیدا می کنند و  شامل کاهش دهنده ها می شود .

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

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

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

 ۱) کاربرد پارامترهای انتخابی قطعه بندی برای استخراج قطعات خروجی

۲) کاربرد پیکسل های سطحی قطعه بندی برای استخراج برچسب نواحی

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

د- wavelet

تحلیل چند کیفیتی (MRA)  برای نمایش سیگنالها و پردازش کیفیت نمایش سیگنالهای تقسیم کننده کیفیت وضوح و فضای مقیاس دهی استفده می شود. و معمولا برای کاهش ابعاد تصویر بکار گرفته می شود . تبدیل wavelet یک ابزار بهینه برای تخمین، فشرده سازی ،حذف نویز و پیدا کردن لبه ها است .می توان از این روش برای قطعه بندی تصاویر متنی نیز استفده نمود. ساختار wavelet بهینه است برای ساختارهای طیفی از داده های ورودی که اغلب برای استخراج ویزگی های تصاویر مورد استفاده قرار می گیرند.

نتیجه گیری

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

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