مقایسۀ مدلهای ارائه شده برای شبکه های اجتماعی برخط با محوریت انجمن های تشکیل شده
شبکههایی که مردم در آنها با یکدیگر متصل و به تولید یا خلق محتوا میپردازند. به عبارتی، امروز گسترش ارتباطات میانفردی در شبکههای اجتماعی مهمترین هدف یا رویکرد در این شبکههاست و حال سوال این است که اتصالات یا روابط (ارتباطات میانفردی) چگونه در شبکههای اجتماعی تحلیل میشوند؟
برای پاسخ به این سوال، روش علمی تحلیل شبکه اجتماعی (Social network analysis) در دنیا مطرح شده است. به عبارتی، تحلیل شبکه اجتماعی، تحلیل روشمند شبکههای اجتماعی است.
تحلیل شبکههای اجتماعی نشاندهنده روابط اجتماعی در نظریه شبکه که متشکل از گرهها (نشاندهنده بازیگران فردی درون شبکه) و روابط (نشاندهنده روابط بین افراد مانند دوستی، خویشاوندی، موقعیت سازمانی و غیره) است. این شبکهها غالبا در دیاگرام شبکههای اجتماعی که در آن گرهها به عنوان نقاط و روابط با خطوط نمایش داده میشود.
شکل1: گراف تحلیل شبکه اجتماعی فیسبوک
روش تحلیل شبکه در پژوهشهای اجتماعی به عنوان پارادایمی مستقل قلمداد میشود چرا که بنیان روشهای پیشنهادی آن مبتنی بر تئوری متمایز و مفروضات هستی شناختی و روششناختی خاصی است که کاملا میان رشتهایست.
تمایز تحلیل شبکه در پژوهشهای علوم اجتماعی و رفتاری با سایر روشها از فرضیه زیربنایی آن مبتنی بر ارتباط بین واحدهای کنش متقابل و اهمیت مفاهیم و اطلاعات رابطهای بین آنهاست و تئوریها، مدلها و کاربردهای آن بر حسب مفاهیم رابطهای یا فرایندها بیان میشود.
تحلیل شبکههای اجتماعی در رشتههای تحصیلی مختلف و همچنین کاربردهای عملی گوناگون مانند مقابله با پولشویی و تروریسم استفاده میشود.
شکل2: گراف تحلیل شبکه اجتماعی توییتر
بالغ بر یک قرن یعنی از اوایل قرن 20 است که مردم، شبکه اجتماعی را برای اشارههای ضمنی به مجموعه روابط پیچیده میان افراد درسیستمهای اجتماعی در تمامی مقیاسها از روابط بین فردی گرفته تا بینالمللی مورد استفاده قرار میدهند.
در سال ۱۹۴۵جان بارنر (J. A. Barnes) برای نخستین بار از اصطلاح تحلیل شبکههای اجتماعی به صوت قاعدهمند برای مشخص کردن الگوهایی از رشتهها استفاده کرد که مفاهیم را مشخص میکنند و به صورت رایج توسط عموم و دانشمندان علوم اجتماعی مورد استفاده قرار میگیرد: گروههای محدود (مانند: قبایل و خانوادهها) و طبقات اجتماعی (مانند: جنسیّت و قومیت).
پیدایش تحلیل شبکه اجتماعی یک تلاش بین رشتهای بوده و مفاهیم آن از تلفیق تئوری اجتماعی با روش شناسی کمی، آماری و ریاضی شکل گرفته و گسترش یافته است. مفاهیم اساسی تحلیل شبکه مانند رابطه، شبکه و ساخت منحصر به رشته خاصی نیست و برآیندی از مطالعات در رشتههای جامعهشناسی، روانشناسی اجتماعی، مردمشناسی، علوم ارتباطات اجتماعی، مهندسی کامپیوتر، ریاضیات و غیره است. [بیشتر بدانید]
گرایشهای تحلیلی متعددی تحلیل شبکههای اجتماعی را تمیز میدهند: هیچ فرضی وجود ندارد که گروهها، بلوکهای بنا کننده اجتماع هستند. تحلیل شبکههای اجتماعی علاوه بر سروکار داشتن با اشخاص (افراد، سازمانها، ایالات) به عنوان واحدهای گسستهتحلیل، برروی چگونگی ساختار رشتهها که اشخاص و روابط میان آنها را تحت تاثیر قرار میدهد نیز تمرکز میکند.
برخلاف تحلیلهایی که بر این فرض استوارند که هنجارهای اجتماعی تعیین کننده رفتارها هستند، تحلیل شبکههای اجتماعی به بررسی وسعت تاثیرگذاری ساختار و ترکیب رشتهها بر هنجارها میپردازد.
در شبکههای اجتماعی برای بررسی چگونگی تأثیرات متقابل میان تشکیلات، توصیف بسیاری از اتصالات غیررسمی که مجریان را به یکدیگر متصل میکند نیز مورد استفاده قرار گرفته است و در این زمینهها نیز به خوبی برقراری ارتباطات فردی میان کارمندان در سازمانهای مختلف عمل میکند.
شبکههای اجتماعی نقش کلیدی در موفقیتهای تجاری و پیشرفتهای کاری ایفا میکنند. شبکهها راه هایی را برای شرکتها فراهم میکنند که اطلاعات جمع آوری کنند، از رقابت بپرهیزند و حتی برای تنظیم قیمتها و سیاستها با هم تبانی کنند.
تحلیل شبکه اجتماعی روش تشخیصی قدرتمندی برای تحلیل طبیعت و الگوی ارتباطات میان اعضای یک گروه خاص است و شامل مجموعهای از روشهای تحلیل گراف است که برای تحلیل شبکهها در علوم مختلف و بین رشتهای توسعه یافته است. به عقیده برت، یک شبکه اجتماعی گروهی از موجودیتهای مشارکتی است که با یکدیگر مرتبط هستند.
اما نکته اساسی این است که تحلیل شبکههای اجتماعی مختص فضا و شبکههای آنلاین نیست، بلکه ابتدا در فضا و شبکههایآفلاین ایجاد و گسترش یافت و در تحقیقات گوناگونی مورد استفاده قرار گرفت.
شکل 3: تحلیل شبکه امانت بینکتابخانهای درایران
به صورت ریاضی، شبکه اجتماعی یک گراف است که در آن هر شرکت کننده در شبکه یک کنشگر 1 خوانده می شود و با یک گره در شبکه نمایش داده می شود. کنشگرها می توانند انسان ها، سازمان ها، گروهها یا هر مجموعه دیگری از موجودیت های مرتبط با هم باشند. ارتباطات میان کنشگرها به وسیله پیوند میان گره های متناظر نمایش داده می شود.
با استفاده از تحلیل شبکه، میتوانید مجموعههای پیچیدهای از روابط را به مثابهی نقشههایی (گراف یا نگارههای گروهی) از سمبلهای متصل تجسم کنید و سنجههای دقیق اندازه شکل و تراکم شبکه را به مثابهی یک کل و موقعیت هر عنصر را درون آن محاسبه نمایید. تحلیل شبکه اجتماعی به شما کمک می کند الگوهای موجود درون مجموعههای نهادهای مرتبط را که شامل مردم هستند، تجسم و بررسی کنید.
تمرکز تحلیل شبکه اجتماعی، میانِ و نه درونِ مردم است. در حالی که در روشهای قدیمیتر تحقیق علوم اجتماعی مانند پیمایشها، بر افراد و ویژگیهایشان (مثل جنسیت، سن و درآمد) تمرکز میکند. تحلیلگران شبکه نه تنها بر کیفیتها و تواناییهای درون آنها تمرکز دارند بلکه توجه ویژهای بر پیوندهایی که افراد را به هم متصل میکنند، نیز دارند.
تحلیل شبکه اجتماعی به دنبال تحلیل روابط و ارتباطات در شبکههای اجتماعی است و اصلا به تحلیل محتوا، متون و سایر عوامل در شبکه نمیپردازد بلکه تنها ارتباطات و روابط را در شبکه بررسی میکند تا مفاهیم علوم اجتماعی را در آن بسنجد.
تحلیل شبکه اجتماعی به محقق این امکان را میدهد تا مفاهیم مختلف علوم اجتماعی از جمله سرمایه اجتماعی، همبستگی اجتماعی، روابط اجتماعی، همریختی اجتماعی و غیره را در شبکههای اجتماعی از طریق فرمولهای نرمافزاری موجود بسنجد یا خود آن مفهوم را به فرمول تبدیل کند و در شبکه مورد آزمایش قرار دهد.
الگوریتم ژنتیک
الگوریتم های ژنتیک (به انگلیسی: Genetic Algorithm)، (با نماد اختصاری GA) تکنیک جستجویی در علم رایانه برای یافتن راهحل تقریبی برای بهینهسازی و مسائل جستجو است. الگوریتم ژنتیک نوع خاصی از الگوریتمهای تکامل است که از تکنیکهای زیستشناسی فرگشتی مانند وراثت و جهش استفاده میکند. این الگوریتم برای اولین بار توسط جان هلند معرفی شد.
در واقع الگوریتمهای ژنتیک از اصول انتخاب طبیعی داروین برای یافتن فرمول بهینه جهت پیشبینی یا تطبیق الگو استفاده میکنند. الگوریتمهای ژنتیک اغلب گزینه خوبی برای تکنیکهای پیشبینی بر مبنای رگرسیون هستند. در هوش مصنوعی الگوریتم ژنتیک (یا GA) یک تکنیک برنامهنویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مسئله استفاده میکند. مسئلهای که باید حل شود دارای ورودیهایی میباشد که طی یک فرایند الگوبرداری شده از تکامل ژنتیکی به راهحلها تبدیل میشود سپس راه حلها بعنوان کاندیداها توسط تابع ارزیاب (Fitness Function) مورد ارزیابی قرار میگیرند و چنانچه شرط خروج مسئله فراهم شده باشد الگوریتم خاتمه مییابد. الگوریتم ژنتیک بطور کلی یک الگوریتم مبتنی بر تکرار است که اغلب بخشهای آن به صورت فرایندهای تصادفی انتخاب میشوند.
این الگوریتمها از بخشهای زیر تشکیل میشوند: تابع برازش – نمایش – انتخاب – تغییر
مقدمه
هنگامی که لغت تنازع بقا به کار میرود اغلب بار ارزشی منفی آن به ذهن میآید. شاید همزمان قانون جنگل به ذهن برسد و حکم بقای قویترها!
البته همیشه هم قویترینها برنده نبودهاند. مثلاً دایناسورها با وجود جثه عظیم و قویتر بودن در طی روندی کاملاً طبیعی بازیِ بقا و ادامه نسل را واگذار کردند در حالی که موجوداتی بسیار ضعیفتر از آنها حیات خویش را ادامه دادند. ظاهراً طبیعت، بهترینها را تنها بر اساس هیکل انتخاب نمیکند! در واقع درستتر آنست که بگوییم طبیعت مناسب ترینها (Fittest) را انتخاب میکند نه بهترینها.
قانون انتخاب طبیعی بدین صورت است که تنها گونههایی از یک جمعیت ادامه نسل میدهند که بهترین خصوصیات را داشته باشند و آنهایی که این خصوصیات را نداشته باشند به تدریج و در طی زمان از بین میروند.
الگوریتمهای ژنتیک یکی از الگوریتمهای جستجوی تصادفی است که ایده آن برگرفته از طبیعت میباشد. الگوریتمهای ژنتیک برای روشهای کلاسیک بهینهسازی در حل مسائل خطی، محدب و برخی مشکلات مشابه بسیار موفق بودهاند ولی الگوریتمهای ژنتیک برای حل مسائل گسسته و غیر خطی بسیار کاراتر میباشند. به عنوان مثال میتوان به مسئله فروشنده دوره گرد اشاره کرد. در طبیعت از ترکیب کروموزومهای بهتر، نسلهای بهتری پدید میآیند. در این بین گاهی اوقات جهشهایی نیز در کروموزومها روی میدهد که ممکن است باعث بهتر شدن نسل بعدی شوند. الگوریتم ژنتیک نیز با استفاده از این ایده اقدام به حل مسائل میکند. روند استفاده از الگوریتمهای ژنتیک به صورت زیر میباشد:
الف) معرفی جوابهای مسئله به عنوان کروموزوم
ب) معرفی تابع فیت نس
ج) جمعآوری اولین جمعیت
د) معرفی عملگرهای انتخاب
ه) معرفی عملگرهای تولید مثل
در الگوریتمهای ژنتیک ابتدا به طور تصادفی یا الگوریتمیک، چندین جواب برای مسئله تولید میکنیم. این مجموعه جواب را جمعیت اولیه مینامیم. هر جواب را یک کروموزوم مینامیم. سپس با استفاده از عملگرهای الگوریتم ژنتیک پس از انتخاب کروموزومهای بهتر، کروموزومها را باهم ترکیب کرده و جهشی در آنها ایجاد میکنیم. در نهایت نیز جمعیت فعلی را با جمعیت جدیدی که از ترکیب و جهش در کروموزومها حاصل میشود، ترکیب میکنیم.
مثلاً فرض کنید گونه خاصی از افراد، هوش بیشتری از بقیه افرادِ یک جامعه یا کولونی دارند. در شرایط کاملاً طبیعی، این افراد پیشرفت بهتری خواهند کرد و رفاه نسبتاً بالاتری خواهند داشت و این رفاه، خود باعث طول عمر بیشتر و باروری بهتر خواهد بود (توجه کنید شرایط، طبیعیست نه در یک جامعه سطح بالا با ملاحظات امروزی؛ یعنی طول عمر بیشتر در این جامعه نمونه با زاد و ولد بیشتر همراه است). حال اگر این خصوصیت (هوش) ارثی باشد بالطبع در نسل بعدی همان جامعه تعداد افراد باهوش به دلیل زاد و ولد بیشترِ اینگونه افراد، بیشتر خواهد بود. اگر همین روند را ادامه دهید خواهید دید که در طی نسلهای متوالی دائماً جامعه نمونه ما باهوش و باهوشتر میشود. بدین ترتیب یک مکانیزم ساده طبیعی توانسته است در طی چند نسل عملاً افراد کم هوش را از جامعه حذف کند علاوه بر اینکه میزان هوش متوسط جامعه نیز دائماً در حال افزایش است.
بدین ترتیب میتوان دید که طبیعت با بهرهگیری از یک روش بسیار ساده (حذف تدریجی گونههای نامناسب و در عین حال تکثیر بالاتر گونههای بهینه)، توانسته است دائماً هر نسل را از لحاظ خصوصیات مختلف ارتقاء بخشد.
البته آنچه در بالا ذکر شد به تنهایی توصیف کننده آنچه واقعاً در قالب تکامل در طبیعت اتفاق میافتد نیست. بهینهسازی و تکامل تدریجی به خودی خود نمیتواند طبیعت را در دسترسی به بهترین نمونهها یاری دهد. اجازه دهید تا این مسأله را با یک مثال شرح دهیم:
پس از اختراع اتومبیل به تدریج و در طی سالها اتومبیلهای بهتری با سرعتهای بالاتر و قابلیتهای بیشتر نسبت به نمونههای اولیه تولید شدند. طبیعیست که این نمونههای متأخر حاصل تلاش مهندسان طراح جهت بهینهسازی طراحیهای قبلی بودهاند. اما دقت کنید که بهینهسازی یک اتومبیل، تنها یک «اتومبیل بهتر» را نتیجه میدهد.
اما آیا میتوان گفت اختراع هواپیما نتیجه همین تلاش بوده است؟ یا فرضاً میتوان گفت فضاپیماها حاصل بهینهسازی طرح اولیه هواپیماها بودهاند؟
پاسخ اینست که گرچه اختراع هواپیما قطعاً تحت تأثیر دستاوردهایهای صنعت اتومبیل بوده است؛ اما بههیچ وجه نمیتوان گفت که هواپیما صرفاً حاصل بهینهسازی اتومبیل و یا فضاپیما حاصل بهینهسازی هواپیماست. در طبیعت هم عیناً همین روند حکمفرماست. گونههای متکاملتری وجود دارند که نمیتوان گفت صرفاً حاصل تکامل تدریجی گونه قبلی هستند.
در این میان آنچه شاید بتواند تا حدودی ما را در فهم این مسأله یاری کند مفهومیست به نام تصادف یا جهش.
به عبارتی طرح هواپیما نسبت به طرح اتومبیل یک جهش بود و نه یک حرکت تدریجی. در طبیعت نیز به همین گونهاست. در هر نسل جدید بعضی از خصوصیات به صورتی کاملاً تصادفی تغییر مییابند سپس بر اثر تکامل تدریجی که پیشتر توضیح دادیم در صورتی که این خصوصیت تصادفی شرایط طبیعت را ارضا کند حفظ میشود در غیر اینصورت به شکل اتوماتیک از چرخه طبیعت حذف میگردد.
در واقع میتوان تکامل طبیعی را به اینصورت خلاصه کرد: جستجوی کورکورانه (تصادف یا Blind Search) + بقای قویتر.
حال ببینیم که رابطه تکامل طبیعی با روشهای هوش مصنوعی چیست. هدف اصلی روشهای هوشمندِ به کار گرفته شده در هوش مصنوعی، یافتن پاسخ بهینه مسائل مهندسی است. بعنوان مثال اینکه چگونه یک موتور را طراحی کنیم تا بهترین بازدهی را داشته باشد یا چگونه بازوهای یک ربات را متحرک کنیم تا کوتاهترین مسیر را تا مقصد طی کند (دقت کنید که در صورت وجود مانع یافتن کوتاهترین مسیر دیگر به سادگی کشیدن یک خط راست بین مبدأ و مقصد نیست) همگی مسائل بهینهسازی هستند.
روشهای کلاسیک ریاضیات دارای دو اشکال اساسی هستند. اغلب این روشها نقطه بهینه محلی (Local Optima) را بعنوان نقطه بهینه کلی در نظر میگیرند و نیز هر یک از این روشها تنها برای مسأله خاصی کاربرد دارند. این دو نکته را با مثالهای سادههای ای روشن میکنیم.
بهینه محلی و بهینه کلی
به شکل زیر توجه کنید. این منحنی دارای دو نقطه ماکزیمم میباشد؛ که یکی از آنها تنها ماکزیمم محلی است. حال اگر از روشهای بهینهسازی ریاضی استفاده کنیم مجبوریم تا در یک بازه بسیار کوچک مقدار ماکزیمم تابع را بیابیم. مثلاً از نقطه ۱ شروع کنیم و تابع را ماکزیمم کنیم. بدیهی است اگر از نقطه ۱ شروع کنیم تنها به مقدار ماکزیمم محلی دست خواهیم یافت و الگوریتم ما پس از آن متوقف خواهد شد. اما در روشهای هوشمند، به ویژه الگوریتم ژنتیک بدلیل خصلت تصادفی آنها حتی اگر هم از نقطه ۱ شروع کنیم باز ممکن است در میان راه نقطه A به صورت تصادفی انتخاب شود که در این صورت ما شانس دستیابی به نقطه بهینه کلی (Global Optima) را خواهیم داشت.
در مورد نکته دوم باید بگوییم که روشهای ریاضی بهینهسازی اغلب منجر به یک فرمول یا دستورالعمل خاص برای حل هر مسئله میشوند. در حالی که روشهای هوشمند دستورالعملهایی هستند که به صورت کلی میتوانند در حل هر مسئلهای به کار گرفته شوند. این نکته را پس از آشنایی با خود الگوریتم بیشتر و بهتر خواهید دید.
الگوریتم ژنتیک چیست؟
الگوریتمهای ژنتیک از اصول انتخاب طبیعی داروین برای یافتن فرمول بهینه جهت پیشبینی یا تطبیق الگو استفاده میکنند. الگوریتمهای ژنتیک اغلب گزینه خوبی برای تکنیکهای پیشبینی بر مبنای رگرسیون هستند.
برای مثال اگر بخواهیم نوسانات قیمت نفت را با استفاده از عوامل خارجی و ارزش رگرسیون خطی ساده مدل کنیم، این فرمول را تولید خواهیم کرد:
قیمت نفت در زمان t = ضریب ۱ نرخ بهره در زمان t + ضریب ۲ نرخ بیکاری در زمان t + ثابت ۱.
سپس از یک معیار برای پیدا کردن بهترین مجموعه ضرایب و ثابتها جهت مدل کردن قیمت نفت استفاده خواهیم کرد. در این روش ۲ نکته اساسی وجود دارد. اول این که روش خطی است و مسئله دوم این است که ما به جای اینکه در میان «فضای پارامترها» جستجو کنیم، پارامترهای مورد استفاده را مشخص کردهایم.
با استفاده از الگوریتمهای ژنتیک ما یک ابر فرمول یا طرح، تنظیم میکنیم که چیزی شبیه «قیمت نفت در زمان t تابعی از حداکثر ۴ متغیر است» را بیان میکند. سپس دادههایی برای گروهی از متغیرهای مختلف، شاید در حدود ۲۰ متغیر فراهم خواهیم کرد. سپس الگوریتم ژنتیک اجرا خواهد شد که بهترین تابع و متغیرها را مورد جستجو قرار میدهد. روش کار الگوریتم ژنتیک به طور فریبندهای ساده، خیلی قابل درک و به طور قابل ملاحظهای روشی است که ما معتقدیم حیوانات آنگونه تکامل یافتهاند. هر فرمولی که از طرح داده شده بالا تبعیت کند فردی از جمعیت فرمولهای ممکن تلقی میشود.
متغیرهایی که هر فرمول دادهشده را مشخص میکنند به عنوان یکسری از اعداد نشان دادهشدهاند که معادلدی. ان. ای آن فرد را تشکیل میدهند.
موتور الگوریتم ژنتیک یک جمعیت اولیه از فرمول ایجاد میکند. هر فرد در برابر مجموعهای از دادههای مورد آزمایش قرار میگیرند و مناسبترین آنها (شاید ۱۰ درصد از مناسبترینها) باقی میمانند؛ بقیه کنار گذاشته میشوند. مناسبترین افراد با هم جفتگیری (جابجایی عناصر دی ان ای) و تغییر (تغییر تصادفی عناصر دی ان ای) کردهاند. مشاهده میشود که با گذشت از میان تعداد زیادی از نسلها، الگوریتم ژنتیک به سمت ایجاد فرمولهایی که دقیقتر هستند، میل میکنند. در حالی که شبکههای عصبی هم غیرخطی و غیرپارامتریک هستند، جذابیت زیاد الگوریتمهای ژنتیک این است نتایج نهایی قابل ملاحظهترند. فرمول نهایی برای کاربر انسانی قابل مشاهده خواهد بود، و برای ارائه سطح اطمینان نتایج میتوان تکنیکهای آماری متعارف را بر روی این فرمولها اعمال کرد. فناوری الگوریتمهای ژنتیک همواره در حال بهبود است و برای مثال با مطرح کردن معادله ویروسها که در کنار فرمولها و برای نقض کردن فرمولهای ضعیف تولید میشوند و در نتیجه جمعیت را کلاً قویتر میسازند.
مختصراً گفته میشود که الگوریتم ژنتیک (یا GA) یک تکنیک برنامهنویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مسئله استفاده میکند. مسئلهای که باید حل شود ورودی است و راه حلها طبق یک الگو کدگذاری میشوند که تابع fitness نام دارد و هر راه حل کاندید را ارزیابی میکند که اکثر آنها به صورت تصادفی انتخاب میشوند.
الگوریتم ژنتیک (GA) یک تکنیک جستجو در علم رایانه برای یافتن راه حل بهینه و مسائل جستجو است. الگوریتمهای ژنتیک یکی از انواع الگوریتمهای تکاملیاند که از علم زیستشناسی مثل وراثت، جهش، انتخاب ناگهانی (زیستشناسی)، انتخاب طبیعی و ترکیب الهام گرفته شده.
عموماً راهحلها به صورت ۲ تایی ۰ و ۱ نشان داده میشوند، ولی روشهای نمایش دیگری هم وجود دارد. تکامل از یک مجموعه کاملاً تصادفی از موجودیتها شروع میشود و در نسلهای بعدی تکرار میشود. در هر نسل، مناسبترینها انتخاب میشوند نه بهترینها.
یک راهحل برای مسئله مورد نظر، با یک لیست از پارامترها نشان داده میشود که به آنها کروموزوم یا ژنوم میگویند. کروموزومها عموماً به صورت یک رشته ساده از دادهها نمایش داده میشوند، البته انواع ساختمان دادههای دیگر هم میتوانند مورد استفاده قرار گیرند. در ابتدا چندین مشخصه به صورت تصادفی برای ایجاد نسل اول تولید میشوند. در طول هر نسل، هر مشخصه ارزیابی میشود وارزش تناسب (fitness) توسط تابع تناسب اندازهگیری میشود.
گام بعدی ایجاد دومین نسل از جامعه است که بر پایه فرایندهای انتخاب، تولید از روی مشخصههای انتخاب شده با عملگرهای ژنتیکی است: اتصال کروموزومها به سر یکدیگر و تغییر.
برای هر فرد، یک جفت والد انتخاب میشود. انتخابها به گونهایاند که مناسبترین عناصر انتخاب شوند تا حتی ضعیفترین عناصر هم شانس انتخاب داشته باشند تا از نزدیک شدن به جواب محلی جلوگیری شود. چندین الگوی انتخاب وجود دارد: چرخ منگنهدار(رولت)، انتخاب مسابقهای (Tournament) ،… .
معمولاً الگوریتمهای ژنتیک یک عدد احتمال اتصال دارد که بین ۰٫۶ و ۱ است که احتمال به وجود آمدن فرزند را نشان میدهد. ارگانیسمها با این احتمال دوباره با هم ترکیب میشوند. اتصال ۲ کروموزوم فرزند ایجاد میکند، که به نسل بعدی اضافه میشوند. این کارها انجام میشوند تا این که کاندیدهای مناسبی برای جواب، در نسل بعدی پیدا شوند. مرحله بعدی تغییر دادن فرزندان جدید است. الگوریتمهای ژنتیک یک احتمال تغییر کوچک و ثابت دارند که معمولاً درجهای در حدود ۰٫۰۱ یا کمتر دارد. بر اساس این احتمال، کروموزومهای فرزند به طور تصادفی تغییر میکنند یا جهش مییابند، مخصوصاً با جهش بیتها در کروموزوم ساختمان دادهمان.
این فرایند باعث به وجود آمدن نسل جدیدی از کروموزومهایی میشود، که با نسل قبلی متفاوت است. کل فرایند برای نسل بعدی هم تکرار میشود، جفتها برای ترکیب انتخاب میشوند، جمعیت نسل سوم به وجود میآیند و … این فرایند تکرار میشود تا این که به آخرین مرحله برسیم.
شرایط خاتمه الگوریتمهای ژنتیک عبارتند از:
روشهای نمایش
قبل از این که یک الگوریتم ژنتیک برای یک مسئله اجرا شود، یک روش برای کد کردن ژنومها به زبان کامپیوتر باید به کار رود. یکی از روشهای معمول کد کردن به صورت رشتههای باینری است: رشتههای ۰و۱. یک راه حل مشابه دیگر کدکردن راه حلها در آرایهای از اعداد صحیح یا اعشاری است، که دوباره هر جایگاه یک جنبه از ویژگیها را نشان میدهد. این راه حل در مقایسه با قبلی پیچیدهتر و مشکلتر است. مثلاً این روش توسط استفان کرمر، برای حدس ساختار ۳ بعدی یک پروتئین موجود در آمینو اسیدها استفاده شد. الگوریتمهای ژنتیکی که برای آموزش شبکههای عصبی استفاده میشوند، از این روش بهره میگیرند.
سومین روش برای نمایش صفات در یک GA یک رشته از حروف است، که هر حرف دوباره نمایش دهنده یک خصوصیت از راه حل است.
خاصیت هر ۳تای این روشها این است که آنها تعریف سازندهایی را که تغییرات تصادفی در آنها ایجاد میکنند را آسان میکنند: ۰ را به ۱ وبرعکس، اضافه یا کم کردن ارزش یک عدد یا تبدیل یک حرف به حرف دیگر.
توضیحات بالا در شکل قابل مشاهده است
یک روش دیگر که توسط 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
شمای کلی شبه کد
ایده اصلی
در دهه هفتاد میلادی دانشمندی از دانشگاه میشیگان به نام جان هلند ایده استفاده از الگوریتم ژنتیک را در بهینهسازیهای مهندسی مطرح کرد. ایده اساسی این الگوریتم انتقال خصوصیات موروثی توسط ژنهاست. فرض کنید مجموعه خصوصیات انسان توسط کروموزومهای او به نسل بعدی منتقل میشوند. هر ژن در این کروموزومها نماینده یک خصوصیت است. بعنوان مثال ژن ۱ میتواند رنگ چشم باشد، ژن ۲ طول قد، ژن ۳ رنگ مو و الی آخر. حال اگر این کروموزوم به تمامی، به نسل بعد انتقال یابد، تمامی خصوصیات نسل بعدی شبیه به خصوصیات نسل قبل خواهد بود. بدیهیست که در عمل چنین اتفاقی رخ نمیدهد. در واقع بصورت همزمان دو اتفاق برای کروموزومها میافتد. اتفاق اول جهش (Mutation) است. «جهش» به این صورت است که بعضی ژنها بصورت کاملاً تصادفی تغییر میکنند. البته تعداد این گونه ژنها بسیار کم میباشد اما در هر حال این تغییر تصادفی همانگونه که پیشتر دیدیم بسیار مهم است. مثلاً ژن رنگ چشم میتواند بصورت تصادفی باعث شود تا در نسل بعدی یک نفر دارای چشمان سبز باشد. در حالی که تمامی نسل قبل دارای چشم قهوهای بودهاند. علاوه بر «جهش» اتفاق دیگری که میافتد و البته این اتفاق به تعداد بسیار بیشتری نسبت به «جهش» رخ میدهد چسبیدن دو کروموزوم از طول به یکدیگر و تبادل برخی قطعات بین دو کروموزوم است. این مسأله با نام Crossover شناخته میشود. این همان چیزیست که باعث میشود تا فرزندان ترکیب ژنهای متفاوتی را (نسبت به والدین خود) به فرزندان خود انتقال دهند.
روشهای انتخاب
روشهای مختلفی برای الگوریتمهای ژنتیک وجود دارند که میتوان برای انتخاب ژنومها از آنها استفاده کرد. اما روشهای لیست شده در پایین از معمولترین روشها هستند.
انتخاب Elitist
مناسبترین عضو هر اجتماع انتخاب میشود.Elitist Selection
انتخاب Roulette
یک روش انتخاب است که در آن عنصری که عدد برازش (تناسب) بیشتری داشته باشد، انتخاب میشود. در واقع به نسبت عدد برازش برای هر عنصر یک احتمال تجمعی نسبت میدهیم و با این احتمال است که شانس انتخاب هر عنصر تعیین میشود.
Roulette Selection
انتخاب Scaling
به موازات افزایش متوسط عدد برازش جامعه، سنگینی انتخاب هم بیشتر میشود و جزئیتر. این روش وقتی کاربرد دارد که مجموعه دارای عناصری باشد که عدد برازش بزرگی دارند و فقط تفاوتهای کوچکی آنها را از هم تفکیک میکند.Scaling Selection
انتخاب Tournament
یک زیر مجموعه از صفات یک جامعه انتخاب میشوند و اعضای آن مجموعه با هم رقابت میکنند و سرانجام فقط یک صفت از هر زیرگروه برای تولید انتخاب میشوند.Tournament Selection
بعضی از روشهای دیگر عبارتند از:Hierarchical Selection, Steady-State Selection, Rank Selection, Tournament Selection
مثال عملی
در این مثال میخواهیم مسئلهٔ ۸ وزیر را بوسیلهٔ این الگوریتم حل کنیم. هدف مشخص کردن چیدمانی از ۸ وزیر در صفحهٔ شطرنج است به نحوی که هیچیک همدیگر را تهدید نکند. ابتدا باید نسل اولیه را تولید کنیم. صفحه شطرنج ۸ در ۸ را در نظر بگیرید. ستونها را با اعداد ۰ تا ۷ و سطرها را هم از ۰ تا ۷ مشخص میکنیم. برای تولید حالات (کروموزومها) اولیه بصورت تصادفی وزیرها را در ستونهای مختلف قرار میدهیم. باید در نظر داشت که وجود نسل اولیه با شرایط بهتر سرعت رسیدن به جواب را افزایش میدهد (اصالت نژاد) به همین خاطر وزیر i ام را در خانهٔ تصادفی در ستون i ام قرار میدهیم (به جای اینکه هر مهرهای بتواند در هر خانه خالی قرار بگیرد). با اینکار حداقل از برخورد ستونی وزیرها جلوگیری میشود. توضیح بیشتر اینکه مثلاً وزیر اول را بطور تصادفی در خانههای ستون اول که با ۰ مشخص شده قرار میدهیم تا به اخر. i=۰،۱، … ۷ حال باید این حالت را به نحوی کمی مدل کرد. چون در هر ستون یک وزیر قرار دادیم هر حالت را بوسیلهٔ رشته اعدادی که عدد k ام در این رشته شمارهٔ سطر وزیر موجود در ستون i ام را نشان میدهد. یعنی یک حالت که انتخاب کردیم میتواند بصورت زیر باشد: ۶۷۲۰۳۴۲۲ که ۶ شمارهٔ سطر ۶ است که وزیر اول که شمارهٔ ستونش ۰ است میباشد تا اخر. فرض کنید ۴ حالت زیر به تصادف تولید شدهاند. این چهار حالت را بعنوان کروموزومهای اولیه بکار میگیریم.
حال نوبت به تابع برازش fitness function میرسد. تابعی را که در نظر میگیریم تابعی است که برای هر حالت تعداد برخوردها (تهدیدها) را در نظر میگیرد. هدف صفر کردن یا حداقل کردن این تابع است. پس احتمال انتخاب کروموزومی برای تولید نسل بیشتر است که مقدار محاسبه شده توسط تابع برازش برای آن کمتر باشد.(روشهای دیگری نیز برای انتخاب وجود دارد) مقدار برازش برای حالات اولیه بصورت زیر میباشد: (مقدار عدد برازش در جلوی هر کروموزوم (با رنگ قرمز)همان تعداد برخوردهای وزیران میباشد)
پس احتمالها بصورت زیر است:
p(۳)>p(۴)>p(۱)>p(۲
در اینجا کروموزومهایی را انتخاب میکنیم که برازندگی کمتری دارند. پس کروموزوم ۳ برای crossover با کروموزومهای ۴ و ۱ انتخاب میشود. نقطهٔ ترکیب را بین ارقام ۶ و ۷ در نظر میگیریم.
۴ و ۳:
۱ و ۳:
حال نوبت به جهش میرسد. در جهش باید یکی از ژنها تغییر کند
. فرض کنید از بین کروموزومهای ۵ تا ۸ کروموزوم شمارهٔ ۷ و از بین ژن چهارم از ۲ به ۳ جهش یابد. پس نسل ما شامل کروموزومهای زیر با امتیازات نشان داده شده میباشد: (امتیازات تعداد برخوردها میباشد)
کروموزوم ۳ کاندیدای خوبی برای ترکیب با ۶ و ۷ میباشد. (فرض در این مرحله جهشی صورت نگیرد و نقطهٔ اتصال بین ژنهای ۱ و ۲ باشد)
کروموزومهای از ۹ تا ۱۲ را نسل جدید میگوییم. بطور مشخص کروموزومهای تولید شده در نسل جدید به جواب مسئله نزدیکتر شدهاند. با ادامهٔ همین روند پس از چند مرحله به جواب مورد نظر خواهیم رسید. پایان
همانطور که در شکل بالا مشاهده می کنید شمای کلی از نحوهٔ عملکرد این الگوریتم را به شما نشان میدهد در ادامه به تعریف و انواع و کابرد این الگوریتم در مسائل می پردازیم.
فرق این مقاله با مقالههای مشابه با این موضوع در این میباشد که در این جا از نگاه کاربردی به الگوریتم های ژنتیکی نگاه شده است و از این منظر در این مقاله به چند نمونه کاربرد این تکنیک در مسائل معروف اشاره شده است. در این مقاله در ابتدا به جایگاه الگوریتم های ژنتیکی و کاربرد آن ها در علم هوش مصنوعی می پردازیم و سپس به توضیح این الگوریتم و انواع آن و همچنین به نحوهٔ نمایش آن می پردازیم. همچنین در انتها به چند منبع برای نمونههای کد باز(متنباز) اشاره می کنیم که خوانندگان در صورت علاقه به کار عملی این الگوریتم را به صورت عملی اجرا کنند تا با عملکرد آن آشنا شوند.
روش جستجوی تکاملی
روش های جستجوی ناآگاهانه، اگاهانه و متاهیوریستیک برای حل مسائل هوش مصنوعی بسیار کارآمد میباشند. همچنین می دانیم که در مورد مسائل بهینه سازی اغلب روش های آگاهانه و ناآگاهانه جوابگوی نیاز ما نخواهند بود. چرا که بیشتر مسائل بهینه سازی در رده مسائل NP قرار دارند. بنابراین نیاز به روش جستجوی دیگری داریم که بتواند در فضای حالت مسائل NP به طرف جواب بهینه سراسری حرکت کند. بدین منظور روش های جستجوی متاهیوریستیک را مطرح می کنیم، این روش های جستجو میتوانند به سمت بهینگی های سراسری مسئله حرکت کنند. در کنار روش های جستجوی متاهیوریستیکی، روش های جستجوی دیگری نیز وجود دارند که به روش های تکاملی معروفند. در ادامه با این نوع الگوریتم بیشتر آشنا می شویم.(لازم به ذکر است که در نگاه کاربردی به الگوریتم های ژنتیکی، اولین قدم در فهم آن، تفهیم الگوریتم های تکامل و تفاوت آن با دیگر الگوریتم های مشابه است.)
نظریه داروین
بر اساس [[نظریه داروین]] نسل هایی که از ویژگی های و خصوصیات برتری نسبت به نسل های دیگر برخوردارند شانس بیشتری نیز برای بقا و تکثیر خواهند داشت و ویژگی ها و خصوصیات برتر آنها به نسل های بعدی آنان نیز منتقل خواهد شد. همچنین بخش دوم نظریه داروین بیان میکند که هنگام تکثیر یک ارگان فرزند، به تصادف رویدادهایی اتفاق می افتد که موجب تغییر خصوصیات ارگان فرزند میشود و در صورتی که این تغییر فایدهای برای ارگان فرزند داشته باشد موجب افزایش احتمال بقای آن ارگان فرزند خواهد شد. در محاسبات کامپیوتری، بر اساس این نظریه داروین روش هایی برای مسائل بهینه سازی مطرح شدند که همه این روش ها از پردازش تکاملی در طبیعت نشات گرفته اند. ما نیز به این روش های جستجو، الگوریتم های جستجوی تکاملی می گوییم.
انواع مختلف الگوریتم های تکاملی
انواع مختلف الگوریتم های تکاملی که تا بحال مطرح شده اند، به شرح زیر میباشد :
الگوریتم ژنتیک
الگوریتم تکاملی
Evolutionary Strategies
Evolutionary Programming
Differential Evolution
Cultural Evolution
Co-evolution
در ادامه قصد داریم بحث خود را بر روی الگوریتم های ژنتیکی سوق دهیم.
الگوریتم ژنتیک
الگوریتم های ژنتیک یکی از الگوریتم های جستجوی تصادفی است که ایده آن برگرفته از طبیعت میباشد . الگوریتم های ژنتیک در حل مسائل بهینه سازی کاربرد فراوانی دارند . به عنوان مثال میتوان به مسئله فروشنده دوره گرد اشاره کرد.(در ادامه با این مسئله و حل آن بیشتر آشنا می شویم) در طبیعت از ترکیب کروموزوم های بهتر، نسل های بهتری پدید میآیند . در این بین گاهی اوقات جهش هایی نیز در کروموزوم ها روی میدهد که ممکن است باعث بهتر شدن نسل بعدی شوند. الگوریتم ژنتیک نیز با استفاده از این ایده اقدام به حل مسائل میکند .
شکل انواع کرموزوم های بدن انسان که در نحوهٔ نمایش گذاری نیز موثر میباشد
کدگذاری و نحوه نمایش
نحوه نمایش جواب مسئله و ژن ها در موفقیت الگوریتم و نحوه پیاده سازی الگوریتم ژنتیک تاثیر بسیار مهمی دارد. در بیشتر مسائل نیز روش های مختلفی برای نشان دادن جواب مساله میتوان طراحی کرد. به عنوان مثال در مسئله 8 وزیر به جای استفاده از بردار( آرایه یک بعدی ) 8 عنصری میتوان از یک ماتریس 8 * 8 استفاده کرد که در آن هر وزیر میتواند در هریک از 64 خانه صفحه شطرنج قرار گیرد. هنگام استفاده از این روش نمایش، در یک خانه ممکن است بیش از یک وزیر قرار گیرد بنابراین هنگام پیاده سازی الگوریتم باید از بروز چنین مسئلهای جلوگیری کنیم.
حل مسائل معروف با استفاده از الگوریتم ژنتیک
یکی از مسائل کلاسیک در الگوریتم های ژنتیک مساله 8 وزیر است. ماهیت مسئله به گونهای است که مدلسازی آن و همچنین اعمال عملگرهای الگوریتم ژنتیک بر روی آن بسیار ساده است. همچنین علاوه برای الگوریتم ژنتیک، روش الگوریتم تبرید شبیهسازی شده نیز در ساده ترین شکل خود برای مسئله چند وزیر نیز روش مناسبی هست همچنین از مسائل مهم دیگری که با استفاده از این الگوریتم قابل حل میباشد مسئلهٔ فروشندهٔ دوره گرد و یا مسئلهٔ چیدمان دینامیک میباشد.
فلو چارت این الگوریتم
منابع