تحقیق مقاله پیاده سازی و ارزیابی الگوریتم ها و سیر تکاملی و انواع زبان های برنامه نویسی

پیاده سازی و ارزیابی الگوریتمها و سیر تکاملی و انواع زبانهای برنامه نویسی

AI به دو مکتب فکری تقسیم می شود:

AI قراردادی (Coventional AI) : توسط رسمی سازی (formalism)، تحلیل آماری، تعاریف و اثبات مشخص می گردد (مثل یادگیری ماشین و سیستم های خبره).

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

شبکه های عصبی

سیستم های فازی

محاسبه تکاملی

الگوریتم های تکاملی تکنیک پیاده سازی مکانیزم هایی مانند تولید مجدد[1] ، جهش، ترکیب مجدد(ادغام)، انتخاب طبیعی (فرایندی که توسط آن افرادی دارای مشخصه های مطلوب با احتمال بیشتری برای تولید افراد بعدی به کار می روند. پس مشخصه های مطلوب در نسل بعد عمومی تر می شوند) و بقای شایسته ترین است. ولی محاسبات تکاملی دارای مشخصه های زیر می باشند:

پیشروی، رشد یا توسعه تکراری

مبنی بر جمعیت

جستجوی تصادفی هدایت شده

پردازش موازی

ملهم از زیست شناسی

محاسبات تکاملی اغلب شامل الگوریتم های بهینه سازی فرااکتشافی است مانند:

الگوریتم های تکاملی (شامل الگوریتم ژنتیک، برنامه نویسی تکاملی، استراتژی تکاملی، برنامه نویسی ژنتیک و سیستم های طبقه بندی کننده یادگیر (Learning Classifier Systems) )

هوش گروهی[2] (شامل بهینه سازی گروه مورچگان و بهینه سازی گروه ذرات[3])

و تا حد کمتری شامل:

خودسازماندهی (نقشه های خودسازمانده ، گاز عصبی در حال رشد، یادگیری رقابتی)

تکامل تفاضلی (دیفرانسیلی)

زندگی مصنوعی

الگوریتم های فرهنگ

سیستم های ایمنی مصنوعی

مدل تکاملی قابل یادگیری

هوش گروهی  (SI) یک تکنیک هوش مصنوعی مبنی بر بررسی رفتار جمعی در سیستم های غیر متمرکز و خودسازمانده است . این واژه توسط Wang  و Beni در سال 1989 و در مبحث سیستم های رباتی سلولی[4] مطرح شد.

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

سیستم های نمونه:

ACO: یک الگوریتم بهینه سازی فرااکتشافی است که می تواند راه حلهای تقریبی را برای مسایل بهینه سازی ترکیبی مشکل بیابد. در ACO، مورچه های مصنوعی با حرکت روی گراف مساله راه حلها را می سازند و با تقلید از مورچه های حقیقی، روی گراف فرومون مصنوعی به جا می گذارند، به نحوی که مورچه های مصنوعی آینده راه حلهای بهتری بیابند. ACO می تواند با موفقیت بر روی مسایل بهینه سازی زیادی اجرا شود. ؟؟؟؟؟؟؟؟؟ مسایل مناسب در مقاله Dorigo

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

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

بهترین سراسری که برای همه شناخته شده است.

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

جستجوی پخشی احتمالی[5]: SDS یک جستجوی سراسری مبنی بر عامل و تکنیک بهینه سازی است که برای مسایلی که تابع هدف می تواند به چندین تابع جزئی مستقل تجزیه شود مناسب است. هر عامل یک فرضیه را نگهداری می کند که به طور مکرر با یک تابع هدف جزئی که به طور تصادفی انتخاب می شود ارزیابی می شود که پارامترهای آن با فرضیه فعلی عامل تعیین می گردد. اطلاعات فرضیه ها از طریق ارتباط بین عاملی در جمعیت پخش می گردد. برخلاف ارتباط stigmergetic  مورد استفاده در ACO، در SDS عاملها فرضیه ها را از طریق استراتژی ارتباطی یک به یک، مبادله می کنند. SDS هم الگوریتم جستجو و هم Optimisation قدرتمند و موثری است که به خوبی به بیان ریاضی توصیف می گردد.

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

EP: اولین بار در 1960 توسط  Lawrence J.Fogel  برای تکامل شبیه سازی شده به عنوان یک فرایند یادگیری با هدف تولید هوش مصنوعی به کار رفت. Fogel ماشینهای حالت متناهی را به عنوان پیشگویی کننده به کار برد و آنها را تکامل داد.

امروزه EP برخلاف سایر گویشها، گویشی از محاسبه تکاملی با ساختار (نمایش) غیرثابت است و به سختی از استراتژی های تکاملی شناخته می شود.

عملگر تغییر اصلی در آن جهش است، اعضای یک جمعیت به جای اعضای یک species به عنوان بخشی از species  خاص درنظر گرفته می شوند، پس هر والد با استفاده از یک انتخاب بازمانده () یک فرزند تولید می کند.

برنامه نویسی ژنتیک(GP)

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

در ابتدا دستورات برنامه و مقادیر داده در قالب ساختارهای درختی سازماندهی می شدند بنابراین از زبانهایی استفاده می شد که به طور طبیعی دارای چنین ساختارهایی بودند مانند Lisp، اما امروزه برنامه­های کامپیوتری در GP می توانند با زبانهای متنوعی نوشته شوند.

الگوریتم ژنتیک(Genetic Algorithm - GA) تکنیک جستجویی در علم رایانه برای یافتن راه‌حل تقریبی برای بهینه‌سازی و مسائل جستجو است. الگوریتم ژنتیک نوع خاصی از الگوریتمهای تکامل است که از تکنیکهای زیست‌شناسی فرگشتی مانند وراثت و جهش استفاده می‌کند.

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

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

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

الگوریتم ژنتیک : الگوریتم ژنتیک که به‌عنوان یکی از روشهای تصادفی بهینه یابی شناخته شده, توسط جان هالند در سال ۱۹۶۷ ابداع شده‌است. بعدها این روش با تلاشهای گلدبرگ ۱۹۸۹, مکان خویش را یافته و امروزه نیز بواسطه تواناییهای خویش , جای مناسبی در میان دیگر روشها دارد. روال بهینه یابی در الگوریتم ژنتیک براساس یک روند تصادفی- هدایت شده استوار می‌باشد. این روش , بر مبنای نظریه تکامل تدریجی و ایده‌های بنیادین داروین پایه گذاری شده‌است.در این روش , ابتدا برای تعدادی ثابت که جمعیت نامیده می‌شود مجموعه‌ای از پارامترهای هدف بصورت اتفاقی تولید می‌شود , پس از اجرای برنامه شبیه ساز عددی را که معرف انحراف معیار و یا برازش آن مجموعه از اطلاعات است را به آن عضو از جمعیت مذکور نسبت می‌دهیم. این عمل را برای تک تک اعضای ایجاد شده تکرار می‌کنیم , سپس با فراخوانی عملگرهای الگوریتم ژنتیک از جمله لقاح , جهش و انتخاب نسل بعد را شکل می‌دهیم و این روال تا ارضای معیار همگرایی ادامه داده خواهد شد.

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

فنوتیپ : ( ویکی : گونه – ریخت، صفات وراثتی )

ژنوتیپ:( آریان پور : نوع معرف و نماینده یک جنس (ازموجودات دارای صفات مشابه ارثی).

در مبحث الگوریتمهای ژنتیک ، افراد، ژنوتیپ[6] نامیده می شوند، درحالیکه راه حلهای کدشده توسط افراد، فنوتیپ[7] نام دارند( از مقاله Blum).

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

همان طور که گفته شد به مجموعه ای از قواعد و دستورالعمل های تعریف شده , زبان برنامه نویسی می گویند.به طور کلی می توان زبان های برنامه نویسی را به صورت زیر تقسیم بندی کرد.
همان طور که در تقسیم بندی ارایه شده ,  مشاهده گردید , زبان های برنامه نویسی با توجه به نزدیکی که به زبان ماشین یا همان0 و 1 دارند به سه دسته تقسیم ; زبان های  سطح پایین بیشتر به زبان ماشین نزدیک هستند و با ظهور اولین نسل از کامپیوتر ها این زبان برنامه نویسی  مورد  استفاده قرار گرفت که برنامه نویسی با آن نیز کار مشکی است. باساخت نسل دوم از کامپیوترها زبان دیگری به نام زبان اسمیلی بوجود آمد که این زبان نیز ه زبان ماشین نزدیک بود ولی استفاده از  آن ساده تر از زبان ماشین است.پس از نسل دوم و ارایه نسل سوم از کامپیوتر ها , زبان های سطح میانی و سطح بالا به وجود آمدند که به زبان محاوره انگلیسی  نزدیک تر بوده و برنامه نویسی با آن ها به مراتب راحت تر از زبان های سطح پایین می باشد. از آن زمان تاکون کیفیت و کمیت زبان هاب برنامه نویسی تغیرات زیادی کرده است و برای تهیه برنامه ها در محیط ها و کاربردهای مختلف زبان های
برنامه نویسی متفاوتی  استفاده می شود. بااین که کار برنامه نویسی زبان های نسل سوم نسبت به  زبان ماشین و اسمبلی آسان تر شده بود اما در پروژه های واقعی و بزرگ کار با این زبان ها سبب سردرگمی برنامه نویسان و پیچیدگی بیش از حد  برنامه ها می شد , بنابراین روند تکامل این زبان ها نیز ادامه پیدا کرد تا این که زبان های سطح بالا از نوع ساخت یافته به وجود آمدند در این روش از برنامه نویسی می توان برنامه ها را به بخش های کوچک تر تقسیم کرد و از آن در هر جایی از برنامه  مورد نظر یا حتی در سایر برنامه ها استفاده نمود. در زبان های سطح بالایی چون پاسکال , C و ویژوال بیسیک می توان از این روش برنامه نویسی استفاده کرد. با وجود محاسن زیادی که این روش برنامه نویسی دارد , اما به دلیل
جدا بودن داده ها از بخش های کوچک تر برنامه , عمل نگهداری داده های با حجم زیاد در آن مشکل است.برنامه نویسی به روش شی گرا , تحولی در این زمینه ایجاد کرد در این روش از برنامه نویسی می توان مجموعه داده ها و دستورالعمل ها را به صورت یک مجموعه بسته بندی کرد واز آن در هر محل از برنامه که لازم است , استفاده کرد, در وافع شما با مفهوم شی آشنا هستید و به شکلی با آن زندگی می کنید , انسان ها , حیوانات و اشیای بی جان مانند اتومبیل
قطار , هواپیما و غیره نمونه های مشخصی از مفهوم شی هستند . هر شی ویژگی ها و خواصی دارد و هر یک از آن ها می توانند در یک یا چند نوع رفتار و عملکرد داشته باشند

[1]  Reproduction

[2]  Swarm Intelligence

[3]  Particle Swarm Optimization

[4]  Cellular Robotic Systems

[5]  Stochastic Diffusion Search

[6] Genotypes

[7] Phenotypes