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

پاورپوینت آشنایی با الگوریتمهای ژنتیک (pptx) 25 اسلاید

دسته بندی : پاورپوینت

نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )

تعداد اسلاید: 25 اسلاید

قسمتی از متن PowerPoint (.pptx) :

آشنایی با الگوریتمهای ژنتیک(GA) آَشنایی با مسایلی که در آنها از GAاستفاده می شود. آشنایی با ساختمان و شیوۀ کار این الگوریتم. TRADITIONAL SEARCHMETHODS روشهای جستجو(Search)را می توان به 3 دسته تقسیم نمود: Search for stored data :Here the problem is to efficiently retrieve information stored in computer memory. Suppose you have a large database of names and addresses stored in some ordered way. What is the best way to search for the record corresponding to a given last name? "Binary search" is one method for efficiently finding the desired record. Knuth (1973) describes and analyzes many such search methods. TRADITIONAL SEARCHMETHODS Search for paths to goals: Here the problem is to efficiently find a set of actions that will move from a given initial state to a given goal. This form of search is central to many approaches in artificial intelligence. A simple example—all too familiar to anyone who has taken a course in AI—is the "8−puzzle," illustrated in figure 1.2. A set of tiles numbered 1–8 are placed in a square, leaving one space empty. Sliding one of the adjacent tiles into the blank space is termed a "move“. Figure (a) illustrates the problem of finding a set of moves from the initial state to the state in which all the tiles are in order. A partial search tree corresponding to this problem is illustrated in figure (b) The "root" node represents the initial state, the nodes branching out from it represent all possible results of one move from that state, and so on down the tree. The search algorithms discussed in most AI contexts are methods for efficiently finding the best (here, the shortest) path. TRADITIONAL SEARCHMETHODS in the tree from the initial state to the goal state. Typical algorithms are “breedth-first search”,”Bidirectional search”,"depth−first search," and "A*.“ TRADITIONAL SEARCHMETHODS Search for solutions: This is a more general class of search than "search for paths to goals." The idea is to efficiently find a solution to a problem in a large space of candidate solutions. These are the kinds of search problems for which genetic algorithms are used. روشهای جستجو برای مسایل بهینه سازی قبل از GA از سال 1940 تاکنون روشهای بهینه سازی متعددی مطرح شده است که به عنوان روشهای کلاسیک شناخته می شوند: برنامه ریزی خطی(Linear Programming) برنامه ریزی غیر خطی(Non Linear programming) برنامه ریزی پویا(Dynamic programming) روش اکتشافی(Inventory) روش زمان بندی(Scheduling) … Genetic Algorithm الگوریتم های ژنتیک که شاخه ای از الگوریتمهای تکاملی است؛ توسط پروفسور Hollanدر دانشگاه میشیگان مطرح گردید. Genetic Algorithm برای مسایلی که در آنها برای ما بهینه بودن مهم است استفاده میشود. GA در مسایلی که ما با فضای بزرگی برای یافتن بهترین جواب روبرو هستیم بهترین کارایی را دارند. البته این نکته قابل ذکر است که GA برای هر مساله قابل پیاده سازی است. GA قادر به دادن جواب قطعی به یک مساله نیست فقط میتواند جواب near optimal به ما دهد. امروزه از این الگوریتم در شاخه های مختلف علوم از قبیل : زیست شناسی علوم فنی و مهندسی(شبکه های عصبی-پردازش تصویر و تشخیص الگو و ...) علوم پایه علوم اجتماعی ... استفاده می کنند. سایر روشهای بهینه سازی Hill climbing Search simulated annealing Search Local beam Search Ant Colony Search ساختمان GA Gene: A gene is a structure embodying a specific item of data encoded in some suitable form. Each gene is equivalent to a functional block of DNA that encode a certain protein. The gene used in genetic algorithm is taken to be atomic. In practical genetic algorithms the genes are used to code the parameters of the problem. Biological chromosomes also contain some genes that contain no information, using such genes in a genetic algorithm increases its stability and allows it to find its objectives faster. Allele: An allele is an allowed value of a gene. In the genetic algorithm an allele is taken to have a bounded range of values this allows genes to be encoded characters or numbers. Chromosome: A Chromosome is a vector of genes that acts as b blue print for the organism. It is possible that genes may be duplicated within a Chromosome and so the position (locus) of the gene within the Chromosome is important. Therefore a Chromosome is often represented as a vector of gene. Population: The population of genetic algorithm is the set of all Chromosomes at same specified point in time.