جان هنری هالند، کسی که تکامل را کامپیوتری و محاسباتی کرد!

مقدمه

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

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

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

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

سرآغاز

جان هنری هالند در 2 فوریه 1929 در فورت وین، ایندیانا (ایالات متحده آمریکا) متولد شد.

رشد

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

دهه 1950

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

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

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

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

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

"من به سیستم‌های پیچیده‌ِی بزرگ و پر سروصدا نگاه می‌کنم و می‌پرسم که چه مکانیسم‌ها و ویژگی‌هایی، مرکزی به نظر می‌رسند."، هالند 1995.

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

او در سال 1954 مدرک کارشناسی ارشد ریاضیات از دانشگاه میشیگان دریافت کرد. بعد از اخد مدرک کارشناسی ارشد در ریاضیات او کار دکترایش را در بخش جدید علوم ارتباطات دانشکده انجام داد. و در سال 1959 اولین دکترای خود را دریافت کرد. آنچه که بعدا علوم کامپیوتر نامیده شد.

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

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

دهه1960

یکی از ایده‌های نوآورانه پروفسور هالند توسعه‌ کدهای کامپیوتری در دهه 1960 بود (هالند به آن‌ها نام الگوریتم ژنتیک را داده بود) که فرایند تکامل را توسط جفت‌گیری و جهش راه‌حل‌های ممکن، تقلیدمی‌کرد؛ که آن‌ها به نوبه خود، راه‌حل‌های جدیدی را به ارمغان می‌آوردند که به یک نتیجه بهینه منجر می‌شدند؛ یک نسخه‌ی کامپیوتری از بقایِ برازنده‌ترین‌ها. 

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

در مقاله یادبود یک اتاق فکر برای مطالعه سیستم‌های پیچیده نقل شده: "این نوع ترجمه دقیق بین دو جامعه فکری، ویژگی یک ذهن بسیار عمیق است."

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

دهه1970

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

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

دهه 1980

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

دکتر هالند ترجیح می‌داد به‌تنهایی کار کند، و می‌گفت:"من دریافته‌ام که اغلب جلسات علمی اتلاف وقت است". او می‌گفت:"من از یادگیری در زمینه‌های مختلف تا حد زیادی لذت می‌برم".

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

دهه 1990

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

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

او ماهیت سیستم‌های پیچیده را در کتاب‌های "نظم پنهان: چگونه پیچیدگی‌ انطباقی، ایجاد می‌کند"(1995) و "ظهور : از آشوب به نظم"(1998) بررسی کرد.

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

 حضور دکتر هالند در گروه مؤسس cscs در سال 1999

 

اعضای cscs سال‌ها پس از تأسیس آن

دهه 2010

در دهه 80 زندگی، او کتاب "سیگنال‌ها و مرز‌ها: بلوک‌های سازنده برای سیستم‌های پیچیده انطباقی"(2012) و "پیچیدگی: مقدمه‌ای بسیار کوتاه"(2014) را به رشته تحریر درآورد.

انگیزه‌ها

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

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

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

دستاورد

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

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

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

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

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

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

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

"من فکر می‌کنم در قلب بسیاری از علوم خلاقانه استعاره‌های خوبی وجود دارند و کار بین‌رشته‌ای منبعی غنی از استعاره است."

درگذشت

دکتر هالند در صبحگاه یکشنبه 9 اوت سال 2015 در خانه‌اش در ان آر بور، میشیگان، در سن 86 سالگی درگذشت. دخترش، گرچن، علت مرگ او را سرطان اعلام کرد. علاوه بر دخترش گرچن بازماندگان دکتر هالند عبارت‌اند از، دو دختر دیگرش به نام‌های آلیسون باتلر و مانجا هالند، خواهرش شیرلی ریگنبرگ و چهار نوه‌اش. دو ازدواج او نهایتاً به جدایی منجر شد.

بی‌شک ایده‌ها، شور و شوق ذهنی و رویکردهای شخصی دکتر هالند چراغی را روشن کرده است که روشنایی‌بخش تحقیق درزمینه¬ی سیستم‌های هوشمند و پیچیده برای سالیان متمادی پیش رو است. 

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

یادش گرامی

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

کتاب "الگوریتم‌های ژنتیک کاربردی" توسط رندی ال هاپت و سو الن هاپت از پژوهشگران ارشد آزمایشگاه تحقیقات کاربردی دانشگاه ایالتی پنسیلوانیا به رشته تحریر درآمده و ویرایش نخست آن در سال 1997 توسط انتشارات وایلی منتشر شده است. همچنین ویرایش دوم این کتاب در سال 2004 عرضه شده است؛ که مهمترین به روز رسانی آن نسبت به ویرایش نخست، کدهای متلبی است که همراه متن آمده‌اند.

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

این کتاب در 7 فصل به انضمام چندین ضمیمه، سازماندهی شده است.

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

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

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

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

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

فصل ششم به مسائل فنی سخت‌تر یورش می‌برد.

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

همچنین ضمیمه1 برخی روتین‌های الگوریتم ژنتیک را به صورت شبه برنامه لیست می‌کند.

در پایان، خواندن کتاب بسیار خوب "الگوریتم‌های ژنتیک کاربردی" توصیه می‌گردد. 

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

الگوریتم ژنتیک دودویی و پاسخ به پنج سوال مهم درباره آن

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

احمدرضا پاکرایی

مقدمه

طی سه پست آتی به توضیح الگوریتم ژنتیک دودویی پرداخته، به پنج سوال مهم در خصوص آن پاسخ می‌دهیم؛ یعنی

چه موضوع مهمی وجود دارد که الگوریتم ژنتیک دودویی را به دردسر می‌اندازد؟

دو دلیل مهم استفاده از عملگر جهش در الگوریتم ژنتیک دودویی چیست؟

در چه مرحله‌ای از اجرای الگوریتم ژنتیک دودویی نباید از عملگر جهش استفاده کرد؟

نخبه‌گرایی در الگوریتم ژنتیک دودویی، به چه موضوع مهمی اشاره دارد؟

نکات کلیدی در به‌کارگیری روش‌های مختلف انتخاب، در الگوریتم ژنتیک دودویی کدامند؟ 

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

الگوریتم ژنتیک: انتخاب طبیعی بر روی کامپیوتر

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

نمایش دودویی متغیر‌ها 

در مقایسه با تکامل بیولوژیک، الگوریتم ژنتیک دودویی نیز با یک جمعیت اولیه از اعضای تصادفی شروع به کار می‌کند. هر رشته باینری(کروموزوم)، ویژگی‌های انتخاب شده‌ی(Selected Characteristics) یکی از اعضای جمعیت را نشان می‌دهد. می‌توان دو رشته‌ای را که به تصادف انتخاب شد‌ه‌اند، با یکدیگر ترکیب کرد در این صورت دو رشته جدید به وجود می‌آیند که ترکیبی از ویژگی‌های دو رشته دیگر هستند؛ پس هر رشته‌ باینری جدید، بخش‌های از رشته‌های باینری والدین خود را شامل می‌شود.  

اجزای الگوریتم ژنتیک دودویی

الگوریتم ژنتیک همانند هر الگوریتم بهینه‌سازی دیگر با تعریف متغیر‌های بهینه‌سازی، تابع هزینه(Cost Function) و هزینه(Cost) شروع می‌شود و مانند سایر الگوریتم‌های بهینه‌سازی با آزمایش همگرایی(Convergence) به پایان می‌رسد. سلسه مراتب اجرای الگوریتم ژنتیک دودویی به صورت یک فلوچارت ساده، در شکل1 نشان داده شده است.

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

تابع هزینه و انتخاب متغیرها 

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

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

الگوریتم ژنتیک به وسیله تعریف یک کروموزوم یا آرایه‌ای از مقادیر متغیرها برای بهینه‌سازی شروع می‌شود. اگر یک کروموزوم $$N_{var}$$ متغیر داشته باشد که توسط$$P_{1},P_{2},P_{3},...,P_{N_{var}}$$   داده شده باشند؛ سپس کروموزوم به صورت یک بردار ردیفی $$N_{var}$$  عنصری نوشته می‌شود.

$$Chromosome=[P_{1},P_{2},P_{3},...,P_{N_{var}}]$$

   هر کروموزوم هزینه‌ای دارد که با ارزیابی تابع هزینه در $$P_{1},P_{2},P_{3},...,P_{N_{var}}$$   تعیین می‌شود.

  $$Cost=f(chromosome)=f(P_{1},P_{2},P_{3},...,P_{N_{var}})$$

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

به زودی در پست بعدی به ادامه مطلب خواهیم پرداخت با ما همراه باشید.

معیارهای ارزیابی قوانین در داده‌کاوی

به نام خدا

مقدمه

معیارهای بسیاری برای ارزیابی عملکرد در یادگیری ماشین و کشف دانش استفاده می‌شود. در استنتاج پیشگویانه (Predictive induction) مبتنی بر دسته‌بندی، اغلب معیار دقت(Accuracy) دسته‌بندی، استفاده می‌شود. در حالیکه سایر معیارهای استاندارد عبارتند از: دقت(Precision)، یادآوری(Recall)، حساسیت(Sensitivity) و اختصاصی کردن(Specificity).

در سایر عملیات‌های کشف دانش مانند قوانین انجمنی که از  جمله روش‌های استنتاج توصیفی(Descriptive Induction) است از معیارهای دیگری نظیر پشتیبانی(Support)، اعتماد(Confidence)، جذابیت(Interestingness) و قابلیت فهم(Comprehensibility) تعریف می‌شود.

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

معیارهای جالب در داده‌کاوی قوانین انجمنی

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

طی سالیان گذشته کارهای بسیاری در زمینه داده‌کاوی به ویژه در زمینه یافتن انجمن‌ها و همبستگی‌ها در میان آیتم‌ها در یک پایگاه داده از تراکنش‌های مشتریان انجام شده است. در زمینه تحلیل سبد خرید(Market Basket Analysis) قوانین انجمنی آیتم‌های را متمایز می‌کند که در اغلب موارد، بخش قابل توجهی از مشتریان، همراه با آیتم‌های خاص دیگری خریداری کرده‌اند. به عنوان مثال ممکن است ما متوجه شویم که 95 درصد از مشتریانی که نان خریده‌اند شیر نیز خریداری کرده‌اند.

هر قانون در داده‌کاوی قوانین انجمنی بایستی دو محدودیت مشخص شده کاربر را برآورده کند؛ یکی معیاری از اهمیت آماری است که پشتیبانی(Support) نامیده می‌شود و دیگری معیاری از خوب بودن قانون است که اعتماد(Confidence) نامیده می‌شود.

در ادامه به تعریف رسمی(Formal Definition) و برخی توضیحات در خصوص تعدادی از معیارهای ارزیابی قوانین انجمنی که در ابتدا معرفی شدند، خواهیم پرداخت.

 

مروری بر مقاله‌ای با عنوان "الگوریتم ممتیکی تکاملی برای استخراج قانون"

به نام خدا

مقدمه

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

 الگوریتم‌های ممتیکی تکاملی EMAs(Evolutionary Memetic Algorithm) بر روی طرح‌هایِ اضافه کردن جستجوی محلی، برای تکمیل قابلیت جستجوی سرتاسری الگوریتم‌های تکاملی EAs، تمرکز دارند.

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

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

در این مقاله دو الگوریتم جستجوی بهبود محلی به کارگرفته شده است؛ یکی از الگوریتم میکروژنتیک μGA استفاده می‌کند که منجر به بهبود کارایی و راهنمایی هدایت شده بر روی نسل‌ها می‌گردد؛ و دیگری AIS(Artificial Immune System) سیستم ایمنی مصنوعی، که به طور گسترده برای تجزیه و تحلیل داده‌ها در الگوریتم‌های یادگیری ماشین بدون ناظر استفاده شده است.

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

در این مقاله دو ضریب پشتیبانی(Support) و اعتماد(Confidence) که از داده‌کاوی قوانین انجمنی به عاریت گرفته شده‌اند در توابع ارزیابی برازندگی استفاده شده است؛ یعنی تابع برازندگی استفاده شده برای ارزیابی مجموعه قوانین، ترکیبی از معیار اصلی یعنی دقت دسته‌بندی به علاوه ایده‌های برگرفته شده از ارزیابی قوانین انجمنی است. قوانین انجمنی قوانینی هستند که تلاش می‌کنند روابط جالب بین متغیر‌ها در یک پایگاه داده را بیابند.

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

 

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

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

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