الگوریتم تکامل فرهنگی Culture Algorithm

مقدمه و تاریخچه الگوریتم تکامل فرهنگی CA

الگوریتم تکامل فرهنگی CA از جمله الگوریتم‌های تکاملی (EAs) هست که از مدل‌های مفهومی فرآیند تکامل فرهنگ انسانی الهام گرفته‌شده‌است. برخلاف الگوریتم‌های تکاملی مرسوم، که فقط بر اساس فضای جمعیت کار می‌کنند، CAها از فضای اضافی به نام فضای باور (belief space) برای جمع‌آوری اطلاعات مربوط به رفتار افراد در فضای جستجو استفاده می‌کنند. از زمان ظهور CA، این الگوریتم‌­ها با موفقیت برای حل طیف گسترده‌ای از مشکلات در شاخه‌های مختلف علم و فناوری گسترش‌یافته‌اند.

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

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

این موارد انگیزه توسعه تکنیک‌های بهینه‌سازی فرا ابتکاری را برای ارائه راه‌حل‌های بهینه یا حداقل تقریباً بهینه، برای این نوع مسائل در زمان معقول ایجاد کرده است. پیشرفت قابل‌توجهی در دهه‌های گذشته در تقلید از پدیده‌های فیزیکی، اکولوژیکی و اجتماعی به‌منظور توسعه الگوریتم‌های فرا ابتکاری به‌عنوان ابزار کارآمد برای یافتن راه‌حل قابل‌قبول برای مسائل پیچیده بهینه‌سازی در دنیای واقعی حاصل‌شده است مثل GA، PSO، BAT و غیره.

پاورپوینت الگوریتم PSO

کلیک کنید

برخلاف تکنیک‌های بهینه‌سازی مبتنی بر گرادیان مرسوم، تکنیک‌های فرا ابتکاری را می‌توان به‌راحتی برای مقابله با مسائل بهینه‌سازی با ویژگی‌های مختلف، مانند غیرخطی بودن، عدم تفکیک‌پذیری، شرطی نشدن نامناسب و چندوجهی اجرا کرد. این تکنیک‌ها را می‌توان بر اساس منبع الهام خود به کلاس‌های مختلفی دسته‌بندی کرد، مانند ­الگوریتم‌های تکاملی (EAs)، الگوریتم‌های SI و الگوریتم‌های الهام گرفته از فیزیک.

الگوریتم‌های تکاملی، الگوریتم‌های فرا ابتکاری الهام گرفته‌شده از بیولوژیک بر اساس نظریه تکامل داروینی هستند که در آن قابلیت‌های بقای گونه‌های زیستی از طریق فرآیندهای طبیعی مانند انتخاب، تولیدمثل و بقای بهترین‌ها بهبود می‌یابد. به‌عنوان مثال، GA، DE  و BBO به دسته EAs تعلق دارند.

پاورپوینت نظریه تکامل داروین — فرگشت و اصول آن

کلیک کنید

ایده استفاده از منابع متعدد دانش در طول فرآیند جستجو با توسعه CAها پدیدار شد. الگوریتم تکامل فرهنگی CA توسعه‌یافته توسط رینولدز در سال ۱۹۹۴ را می‌توان به‌عنوان یک الگوریتم تکاملی طبقه‌بندی کرد. ضمنا این الگوریتم براساس مدل‌های مفهومی فرآیند تکامل فرهنگی انسان است “در طول زمان، انسان‌ها مجموعه ای از قابلیت‌ها را تکامل داده‌اند که از آموزش، کدگذاری و انتقال اطلاعات فرهنگی پشتیبانی می‌کند.”

برخلاف EA های مرسوم که فقط براساس فضای جمعیت کار می‌کنند، CA ها یا الگوریتم‌های فرهنگی همانطور که قبلا نیز اشاره شد، از فضای اضافی به نام فضای باور برای جمع‌آوری اطلاعات مربوط به رفتار افراد در فضای جستجو استفاده می‌کنند. الگوریتم‌های فرهنگی را می‌توان بسط الگوریتم‌های ژنتیک در نظر گرفت. در ادامه سورس کد مقایسه الگوریتم های بهینه سازی در متلب در محیط Matlab 2014b نوشته و اجرا شده است. در این سورس کد به مقایسه ۱۲ الگوریتم بهینه سازی و نتایج حاصل از آن‌ها پرداخته شده است.

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

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

کلیک کنید

ایده اصلی الگوریتم فرهنگی CA

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

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

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

فلوچارت الگوریتم تکامل فرهنگی CA

فلوچارت بالا چارچوب کلی و اجزای اصلی CA را نشان می‌دهد. برخلاف EA های معمولی که از یک فضای جمعیتی تشکیل‌شده‌اند، الگوریتم فرهنگی روی دو فضا کار می‌کند که عبارت‌اند از جمعیت و باور. تعامل بین جمعیت و فضاهای اعتقادی از طریق پروتکل ارتباطی، یعنی توابع پذیرش و تأثیر گذاری یا نفوذ فراهم می‌شود.

مانند سایر EAهای مبتنی بر جمعیت، فضای جمعیت CAها یک جزء ژنتیکی حاوی راه حل‌های فردی است که در سطح ژنوتیپی و یا فنوتیپی (مربوط به ویژگی‌های قابل‌مشاهده یک فرد ناشی از تعامل ژنوتیپ آن با محیط) نشان داده می‌شوند. درحالی‌که فضای باور نشان‌دهنده اطلاعات فرهنگی به‌دست‌آمده در طول فرآیند تکامل است.

به زبان ساده‌تر اگر بخواهیم توضیح بدهیم در CA فرآیند یادگیری در هردوی این فضاها به‌طور همزمان انجام می‌شود در جامعه یک امر بده بستان بین فرهنگ و جمعیت داریم. ارتباط جمعیت با فرهنگ بحث پذیرش آن فرهنگ هست. ارتباط فرهنگ بر جمعیت همان بحث تأثیر گذاری آن است. بر روی خود فضای فرهنگ اتفاقاتی می‌افتد و تأثیراتی مانند تغییر فضای باور انجام می‌شود.

تاثیرات انجام‌شده در جمعیت یک امر انتخابی است مثل همان اتفاقی که در الگوریتم ژنتیک داشتیم یعنی انتخاب اعضایی که به دلایل قوی بودن تأثیر بیشتری بر روی جمعیت می‌گذارند موضوع بعدی تابع ارزیابی است. هر چیزی که در فضای جمعیت داریم باید طبق این تابع ارزیابی شوند. در این بخش پکیج حل مسئله فروشنده دوره گرد با الگوریتم ژنتیک در پایتون قرار داده شده است. این پکیج شامل سورس کد حل مسئله، گزارش کار ۱۲ صفحه‌ای از روند کدنویسی و یک فیلم آموزشی ۴۰ دقیقه‌ای می‌باشد.

• حل مسئله فروشنده دوره گرد با الگوریتم ژنتیک | راهنمای جامع حل مسئله در پایتون در ۷ گام

مسئله بعدی تغییر جمعیت است می‌تواند به‌صورت cross over یا mutation همان جهش، باشد با این دو مورد در الگوریتم ژنتیک آشنا هستیم یا حالا هر چیزی که امیدواریم با انجام آن جواب‌های متفاوت و البته بهتر به‌دست بیاوریم. در بحث جمعیت عملیات انتخاب، تابع بررسی ارزیابی و تغییر جمعیت یا تنوع جمعیت در تمام الگوریتم‌های تکاملی وجود دارد. درواقع عملیاتی که در الگوریتم‌های تکاملی داشتیم اگر فرهنگ را دخیل کنیم نتیجه الگوریتم تکامل فرهنگی CA خواهد بود.

شبه کد الگوریتم فرهنگی CA

Set the generation counter, t=0;
Create and initialize the population space , PS(t);
Create and initialize the belief space , BS(t);
While stopping criterion is met do
       t=t+1;             
Evaluate the fitness of each individuals in PS (t) using Obj() 
       Accept some elite individuals from the PS(t) using Accept()
       Update B (t) using Update()
       Produce new generation 𝑃𝑆(𝑡 + ۱) using 𝐼𝑛𝑓𝑙𝑢𝑒𝑛𝑐𝑒() 
end

فضای باور در الگوریتم تکامل فرهنگی CA

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

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

دانش موقعیتی یا وضعی (Situational knowledge)

منبع دانش موقعیتی یا وضعی نشان داده‌شده توسط بهترین تجربه افراد در هر نسل از فضای جمعیت را ذخیره می‌کند. وضعیت فضای فرهنگ را بصورت به‌عنوان‌مثال باسوادترین، باهوش‌ترین، ثروتمندترین، بهترین نویسنده یا حتی بدترین، تأثیرگذارترین فرد در محیط دانشگاهی و آکادمیک چه کسایی بودند را مشخص می‌کنیم. بهترین راه‌حلی که تا حالا پیداشده یا بهترین هر نسل جزو این مؤلفه است. این موارد مؤلفه‌های وضعی هستند. مؤلفه دانش وضعی توسط تابع 𝑈𝑝𝑑𝑎𝑡𝑒 به‌صورت زیر به‌روز می‌شود.

که  X^t_l در فرمول بالا l امین فرد پذیرفته‌شده در تکرار t است و n accept تعداد نشان‌دهنده تعداد افراد نخبه پذیرفته‌شده برای به‌روزرسانی فضای اعتقادی است.

دانش هنجاری (Normative knowledge)

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

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

دانش توپوگرافیک (Topographical knowledge)

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

دانش محدوده (Domain knowledge)

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

دانش تاریخچه (History knowledge)

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

• بیشتر بخوانید — کد الگوریتم ژنتیک در c++ بصورت رایگان و کاربردی

پروتکل ارتباطی در الگوریتم تکامل فرهنگی CA

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

تابع پذیرش

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

انتخاب درصد معینی از افراد، از ۱% تا ۱۰۰% برای به‌روز رسانی فضای باور بسته به عملکرد الگوریتم در یک برنامه خاص بسیار رایج است. در توابع پذیرش پویا، تعداد افراد انتخاب‌شده برای به‌روز رسانی باورها ثابت نیست و از نسلی به نسل دیگر متفاوت است.

تابع تاثیر

در یک جامعه انسانی واقعی، افراد از باورهای جهانی پیروی می‌کنند که توسط نسل‌های گذشته کسب‌شده و به نسل کنونی رسیده است. به‌منظور مدل‌سازی این پدیده، CAها از توابع تأثیر برای تأثیرگذاری بر فضای جمعیت و ایجاد نسل جدیدی از افراد استفاده می‌کنند.

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

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

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

سخن آخر در مورد کاربرد الگوریتم فرهنگی CA

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