رایانش نرم

رایانش نرم

اسلاید 1: Soft ComputingEsmat RashediElectrical Eng. Dept.,KGUT, Kerman, Iran.1In the name of God

اسلاید 2: رايانش نرم2

اسلاید 3: optimizationMinimizationMaximizationکمينه يابیبيشينه يابی3

اسلاید 4: Optimization problemفرض کنيد که هدف از بهينه­سازي، پيدا کردن بيشينه تابع f در يک دامنه مشخص باشد:در اين وضعيت، پيدا کردن مقاديري براي متغيرهاي تا مد نظر است که تابع f، به ازاي آنها بيشترين مقدار را به خود بگيرد.به عبارتي هدف از بيشنه­سازي، يافتن است به گونه­اي که 4

اسلاید 5: Decision variablesمتغيرهای مساله Variablesفضای جستجو search spacem=2m=35

اسلاید 6: Search spaceSearch space is the m-dimensional space that determined by the boundaries of variables.Agents search this space to find the best settings for variables.6x1x2x3m=3

اسلاید 7: تابع هدف Objective functionm=27

اسلاید 8: OptimizationMethods of optimizationDerivative based methods (gradient base)Derivative freeمبتنی بر مشتق / بی نياز از مشتقExhaustive Search جستجوی همه جانبهRandom search جستجوی تصادفی8

اسلاید 9: Classic OptimizationLet Ɵ be an unknown parameter vector and J (Ɵ ) the corresponding cost function to be minimized. Function J (Ɵ ) is assumed to be differentiable.Gradient descent algorithmThe algorithm starts with an initial estimate Ɵ(0) of the minimum point and the subsequent algorithmic iterations are of the form:where µ> 0. If a maximum is sought, the method is known as gradient ascent and the minus sign in (C.2) is neglected.9

اسلاید 10: Gradient descent algorithmThe new estimate Ɵ(new) is chosen in the direction that decreases J(Ɵ).The parameter µ is very important and it plays a crucial role in the convergence of the algorithm.If it is too small, the corrections ΔƟ are small and the convergence to the optimum point is very slow.if it is too large, the algorithm may oscillate around the optimum value and convergence is not possible10

اسلاید 11: Gradient descent algorithmHowever, if the parameter is properly chosen, the algorithm converges to a stationary point of J (Ɵ ) , which can be either, a local minimum (Ɵ 1) or a global minimum (Ɵ) or a saddle point (Ɵ2).it converges to a point where the gradient becomes zero.To which of the stationary points the algorithm will converge depends on the position of the initial point, relative to the stationary points11

اسلاید 12: Random searchدر روشهاي دسته ب، برای جستجوي بهينه در يک مسئله نيازي به مشتق تابع هدف نيست. در عوض اين روشها به دفعات به ارزيابي تابع هدف به ازاي نقاطي از دامنه جستجوي مسئله مي­پردازند و با استفاده از اين اطلاعات و در نظر گرفتن يکسري الهامات شهودي جهت جستجو را تعيين مي­کنند. جستجوي ابتکاري (Heuristic search algorithms) ارائه راه حلهاي خوب (نزديک بهينه) در يک زمان قابل قبولتضميني برای يافتن جواب بهينه (بهترين جواب) نمي­دهندفضاي جستجو را بطور همه جانبه جستجو نمي کنند پس جزء روشهاي جستجوي تقريبي بشمار مي آيندمنبع الهام اين الگوريتم ها غالبا طبیعت است.12

اسلاید 13: Heuristic algorithms: Examples- Evolutionary algorithm الگوريتم تکاملی- Genetic Algorithm (GA) الگوريتم وراثتی- Simulated annealing پخت شبيه سازی شده- Ant colony search algorithm (ACSA) / (ACO) الگوريتم جستجوی جمعيت مورچگان- Particle Swarm Optimization (PSO) بهينه سازی جمعيت ذرات - Tabu search جستجوی تابو- Scatter search جستجوی پراکنده- Immune system سيستم ايمنی- Gravitational search algorithm (GSA) الگوريتم جستجوی گرانشی13

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

اسلاید 15: OptimumLocal optimum بهينه محلیGlobal optimum بهينه فرا محلیSub optimum شبه بهينه15

اسلاید 16: قالب کلی الگوريتم­هاي جستجوي ابتکاري16

اسلاید 17: Population17فضای جستجوی چند بعدیيک عضو جمعيت 

اسلاید 18: قالب کلی18ارزيابی اعضاءاجرای عملگرهاتوليد اعضاء جديد به کمک عملگرهای الگوريتم operatorsانجام می شود.هر الگوريتم تعدادی عملگر ساده دارد.الگوريتم تکرارشونده است. هر تکرار يک iteration يا يک time ناميده می شود. (تکرار يا لحظه)ارزيابی اعضاءاجرای عملگرهاارزيابی اعضاءاجرای عملگرهاt=1t=2t=T

اسلاید 19: General form of the population based heuristic search algorithms19StartSettingsRandom initializationEvaluationoperatorsEnd criteria?Print best resultNoYes

اسلاید 20: ويژگی های الگوريتم های جستجوی (بهینه سازی) ابتکاریOptimization Search algorithmsHeuristic algorithmsPopulation based (Agents) Iterative searchRandom searchParallel search 20

اسلاید 21: ConvergenceExploration / diversificationExploitation / intensification21t=1t=2t=Tt=T-1

اسلاید 22: Evaluationارزيابی اعضا در ابتدای هر تکرار انجام می شود.تعداد کل ارزيابی هاTotal Number of fitness evaluations (FEs)22  حل مساله

اسلاید 23: ComparisonExperiments and comparisonالگوريتم ها از طريق آزمايش و مقايسه با ساير روش ها بررسی می شوند.معيار مقايسه دقت جواب ها و زمان رسيدن به پاسخ است.23

اسلاید 24: Various Versions of algorithmsSingle objective تک هدفهMulti-objective چند هدفهUn-constraint نامقيدConstraint مقيدReal حقيقیBinary باينریDiscrete گسسته24