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

بخشی از مقاله

پياده سازي و ارزيابي الگوريتمها و سير تكاملي و انواع زبانهاي برنامه نويسي

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

دهاي آزمون و خطا شناخته مي شود. هوش محاسباتي به سه بخش اصلي تقسيم مي گردد:
a. شبکه هاي عصبي
b. سيستم هاي فازي
c. محاسبه تکاملي

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

 ملهم از زيست شناسي

محاسبات تکاملي اغلب شامل الگوريتم هاي بهينه سازي فرااکتشافي است مانند:
- الگوريتم هاي تکاملي (شامل الگوريتم ژنتيک، برنامه نويسي تکاملي، استراتژي تکاملي، برنامه نويسي ژنتيک و سيستم هاي طبقه بندي کننده يادگير (Learning Classifier Systems) )
- هوش گروهي (شامل بهينه سازي گروه مورچگان و بهينه سازي گروه ذرات )
و تا حد کمتري شامل:
- خودسازماندهي (نقشه هاي خودسازمانده ، گاز عصبي در حال رشد، يادگيري رقابتي)
- تکامل تفاضلي (ديفرانسيلي)
- زندگي مصنوعي
- الگوريتم هاي فرهنگ
- سيستم هاي ايمني مصنوعي
- مدل تکاملي قابل يادگيري

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

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

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

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

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

ک به يک، مبادله مي کنند. SDS هم الگوريتم جستجو و هم Optimisation قدرتمند و موثري است که به خوبي به بيان رياضي توصيف مي گردد.
کاربرد تکنيکهاي مبني بر هوش گروهي : کنترل خودروهاي بدون سرنشين، نقشه برداري نجومي.
EP: اولين بار در 1960 توسط Lawrence J.Fogel براي تکامل شبيه سازي شده به عنوان يک فرايند يادگيري با هدف توليد هوش مصنوعي به کار رفت. Fogel ماشينهاي حالت متناهي را به عنوان پيشگويي کننده به کار برد و آنها را تکامل داد.
امروزه EP برخلاف ساير گويشها، گويشي از محاسبه تکاملي با ساختار (نمايش) غيرثابت است و به سختي از استراتژي هاي تکاملي شناخته مي شود.
عملگر تغيير اصلي در آن جهش است، اعضاي يک جمعيت به جاي اعضاي يک species به عنوان بخشي از species خاص درنظر گرفته مي شوند، پس هر والد با استفاده از يک انتخاب بازمانده ( ) يک فرزند توليد مي کند.

برنامه نويسي ژنتيک(GP)
يک متدولوژي خودکار الهام گرفته شده از تکامل زيستي است براي يافتن برنامه هاي کامپيوتري که الگوريتمي تکاملي را براي بهينه کردن جمعيتي از برنامه هاي کامپيوتري برحسب چشم انداز شايستگي تعيين شده توسط توانايي برنامه براي انجام وظيفه محاسباتي داده شده به کار مي رود.
در ابتدا دستورات برنامه و مقادير داده در قالب ساختارهاي درختي سازماندهي مي شدند بنابراين از زبانهايي استفاده مي شد که به طور طبيعي داراي چنين ساختارهايي بودند مانند Lisp، اما امروزه برنامه¬هاي کامپيوتري در GP مي توانند با زبانهاي متنوعي نوشته شوند.

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

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

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

دارد. روال بهينه يابي در الگوريتم ژنتيک براساس يک روند تصادفي- هدايت شده استوار مي‌باشد. اين روش , بر مبناي نظريه تکامل تدريجي و ايده‌هاي بنيادين داروين پايه گذاري شده‌است.در اين روش , ابتدا براي تعدادي ثابت که جمعيت ناميده مي‌شود مجموعه‌اي از پارامترهاي هدف بصورت

اتفاقي توليد مي‌شود , پس از اجراي برنامه شبيه ساز عددي را که معرف انحراف معيار و يا برازش آن مجموعه از اطلاعات است را به آن عضو از جمعيت مذکور نسبت مي‌دهيم. اين عمل را براي تک تک اعضاي ايجاد شده تکرار مي‌کنيم , سپس با فراخواني عملگرهاي الگوريتم ژنتيک از جمله لقاح , جهش و انتخاب نسل بعد را شکل مي‌دهيم و اين روال تا ارضاي معيار همگرايي ادامه داده خواهد شد.
بصورت متداول سه معيار به‌عنوان معيار توقف شمرده مي‌شود: I. زمان اجراي الگوريتم II. تعداد نسلهايي که ايجاد مي‌شوند III. همگرايي معيار خطا

فنوتيپ : ( ويکي : گونه – ريخت، صفات وراثتي )
ژنوتيپ:( آريان پور : نوع معرف و نماينده يك جنس (ازموجودات داراي صفات مشابه ارثي).
در مبحث الگوريتمهاي ژنتيک ، افراد، ژنوتيپ ناميده مي شوند، درحاليکه راه حلهاي کدشده توسط افراد، فنوتيپ نام دارند( از مقاله Blum).
همان طور كه مي دانيد كامپيوتر از دو جز اصلي سخت افزار و نرم افزار تشكيل شده است بنابراين براي استفاده از هر كامپيوتر لازم است تا داده ها و دستورالعمل ها براي پردازش به آن داده شودو نتيجه پردازش داده ها يعمي اطلاعات ارايه گردد يا به عبارت ديگر كاربر بتواند با سخت افزار ارتباط برقرار كند. در اينجاست كه نقش نرم افزار به عنوان يكي ازاجزاي اصلي در كامپيوتر كاملاً قابل مشاهده است دراين مقاله شما را با تعريف و تاريخچه توليد و طراحي زبان هاي برنامه نويسي از ابتدا تا امروز آشنا خواهيم كرد.نرم افزار ها مجموعه اي از داده ها و دستورالعمل ها هستند كه به وسيله برنامه نويس و بر اساس قواعد مشخص , نوشته مي شوند و سخت افزار را قابل استفاده مي كنند. نرم افزارهابه دو دسته كلي سيستمي و كاربردي تقسيم مي شوند در شكل زير انواع نرم افزارها را مشاهده مي كنيد.

1-1 تقسيم بندي زبان هاي برنامه نويسي
همان طور كه گفته شد به مجموعه اي از قواعد و دستورالعمل هاي تعريف شده , زبان برنامه نويسي مي گويند.به طور كلي مي توان زبان هاي برنامه نويسي را به صورت زير تقسيم بندي كرد.

همان طور كه در تقسيم بندي ارايه شده , مشاهده گرديد , زبان هاي برنامه نويسي با توجه به نزديكي كه به زبان ماشين يا همان0 و 1 دارند به سه دسته تقسيم ; زبان هاي سطح پايين بيشتر به زبان ماشين نزديك هستند و با ظهور اولين نسل از كامپيوتر ها اين زبان برنامه نويسي مورد

استفاده قرار گرفت كه برنامه نويسي با آن نيز كار مشكي است. باساخت نسل دوم از كامپيوترها زبان ديگري به نام زبان اسميلي بوجود آمد كه اين زبان نيز ه زبان ماشين نزديك بود ولي استفاده از آن ساده تر از زبان ماشين است.پس از نسل دوم و ارايه نسل سوم از كامپيوتر ها , زبان هاي

سطح مياني و سطح بالا به وجود آمدند كه به زبان محاوره انگليسي نزديك تر بوده و برنامه نويسي با آن ها به مراتب راحت تر از زبان هاي سطح پايين مي باشد. از آن زمان تاكون كيفيت و كميت زبان هاب برنامه نويسي تغيرات زيادي كرده است و براي تهيه برنامه ها در محيط ها و كاربردهاي مختلف زبان هاي

برنامه نويسي متفاوتي استفاده مي شود. بااين كه كار برنامه نويسي زبان هاي نسل سوم نسبت به زبان ماشين و اسمبلي آسان تر شده بود اما در پروژه هاي واقعي و بزرگ كار با اين زبان ها سبب سردرگمي برنامه نويسان و پيچيدگي بيش از حد برنامه ها مي شد , بنابراين روند تكامل اين زبان ها نيز ادامه پيدا كرد تا اين كه زبان هاي سطح بالا از نوع ساخت يافته به وجود آمدند در اين روش از برنامه نويسي مي توان برنامه ها را به بخش هاي كوچك تر تقسيم كرد و از آن در هر جايي از برنامه مورد نظر يا حتي در ساير برنامه ها استفاده نمود. در زبان هاي سطح بالايي چون پاسكال , C و ويژوال بيسيك مي توان از اين روش برنامه نويسي

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

برنامه نويسي به روش شي گراء از همين مفاهيم موجود در طبيعت و اطراف ما استفاده مي كند و داده و دستورالعمل هاي مورد نظر در رابطه با پردازش روي داده ها رابه صورت مجموعه اي به نام شي گرد آوري و استفاده مي كند. از معروف ترين زبان هاي شي گرا مي توان به زبان برنامه نويسي ++C, ويژوال بيسيك و دلفي اشاره كرد. اين زبان ها علاوه بر ويژگي ساخت يافته , از ويژگي شي گرايي نيز بهره مند هسنتد . البته زبان برنامه نويسي ويژوال بيسيك از تمام امكانات روش شي گرايي مانند++C برخوردار نيست و به عبارت ديگر ويژوال بيسيك مي تواند به صورت

شيئي گرا نيز مورد استفاده قرار گيرد.زبان هاي برنامه نويسي علاوه بر تقسيم هاي ارايه شده (صرف نظر از سطح آنها), از نظر نحوه ترجمه و اجراي دستورالعمل هاي يك برنامه نيز تقسيم بندي مي شوند.در اين تقسيم بندي زبان هاي برنامه نويسي شامل دو گروه مفسرها ( Interpreter ) و مترجم ها ( Compiler ) مي شوند. زبان برنامه نويسي كه از نوع مفسر است , دستورالعمل هاي برنامه را به ترتيب از بالا به پايين اجرا مي كند و براي اين كار هر خط از برنامه را به زبان ماشين ترجمه كرده و در صورت

عدم وجود خطاي نوشتاري آن را اجراء مي كند; سپس خط بعدب را ترجمه و اجرا مي كند و به همين صورت خطوط برنامه را يكي يكي و به ترتيب ترجمه و اجرا مي شوند . بنابراين همواره لازم است تا برنامه را در محيط زبان برنامه نويسي اجراء كرد و ايجاد برنامه مستقل ( Application ) امكان پذير نيست , به عنوان نمونه مي توان به زبان برنامه نويسي GWBASIC اشاره نمود.برخلاف زبان هاي برنامه نويسي از نوع مفسر , يك زبان برنامه نويسي از نوع مترجم ابتدا تمام دستوالعمل هاي برنامه را به طور هم زمان و يك جا به زبان ماشين ترجمه مي كند و درصورت عدم وجود خطاي نوشتاري برنامه ترجمه شده را اجراء مي كند; به عبارت ديگر اين گونه زبان هاي برنامه نويسي برنامه نوشته شده را كه به آن برنامه

منبع(Source)
مي گويند و به زبان ماشين كه به آن برنامه مقصد ( Object ) مي گويند , تبديل مي كنند و سپس آنرا اجرا مي نمايند.