Title: Soft Computing Author: Eva Volná, University of Ostrava, Czech Republic Název: Soft Computing Autor: Eva Volná, University of Ostrava, Czech Republic Soft computing se stal oficiální oblastí studia informatiky na počátku 90. let. Prof. Lotfi Aliasker Zadeh definoval soft computing jako řadu technik a metod, které řeší reálné situace stejným způsobem, jakým by je řešili lidé. V informatice je soft computing (někdy nazývaný výpočetní inteligence - Computational Intelligence CI) používán pro nepřesná řešení výpočetně náročných úkolů, jako je řešení NP-úplných problémů, pro které neexistuje žádný známý algoritmus, který by dokázal vypočítat přesná řešení v polynomiálním čase. Soft computing se liší od konvenčních výpočtů tím, že na rozdíl od nich je tolerantní k nepřesnosti, nejistotě, částečné pravdě a přiblížení. Modelem pro soft computing je ve skutečnosti lidská mysl. Soft computing tvoří základ značného množství metod strojového učení. Hlavní komponenty soft computingu jsou fuzzy logika, evoluční výpočty a neuronové sítě. Obecně řečeno, techniky soft computingu se podobají biologickým procesům více než tradičním technikám, které jsou zejména založeny na formálních logických systémech. Techniky soft computingu se vzájemně doplňují. Soft computing sa stal oficiálnou oblasťou štúdia informatiky na začiatku 90. rokov. Prof. Lotfi Aliasker Zadeh definoval soft computing ako rad techník a metód, ktoré riešia reálne situácie rovnakým spôsobom, akým by ich riešili ľudia. V informatike je soft computing (niekedy nazývaný výpočtová inteligencia - Computational Intelligence CI) používaný pre nepresné riešenia výpočtovo náročných úloh, ako je riešenie NP-úplných problémov, pre ktoré neexistuje žiadny známy algoritmus, ktorý by dokázal vypočítať presná riešenie v polynomiálním čase. Soft computing sa líši od konvenčných výpočtov tým, že na rozdiel od nich je tolerantný k nepresnosti, neistote, čiastočnej pravde a priblíženiu. Modelom pre soft computing je v skutočnosti ľudská myseľ. Soft computing tvorí základ značného množstva metód strojového učenia. Hlavné komponenty soft computingu sú fuzzy logika, evolučné výpočty a neurónové siete. Všeobecne povedané, techniky soft computingu sa podobajú biologickým procesom viac ako tradičným technikám, ktoré sú založené najmä na formálnych logických systémoch. Techniky soft computingu sa vzájomne dopĺňajú. Fuzzy logika. Fuzzy logika je založena na teorii fuzzy množin, což je zobecnění klasické teorie množin. Klasická logika povoluje pouze závěry, které jsou buď pravdivé, nebo nepravdivé. Ve fuzzy logice mohou být pravdivostní hodnoty proměnných libovolná reálná čísla mezi 0 a 1 včetně. Proto je funkce příslušnosti prvku k fuzzy množině definována jako křivka, která určuje, jak je každý bod ve vstupním prostoru mapován na hodnotu mezi 0 a 1. Vstupní prostor je označován jako univerzum diskurzu. Univerzum diskurzu proměnné X je spojitý prostor a obvykle jej rozdělujeme do několika fuzzy množin. Tyto fuzzy množiny se nazývají jazykové proměnné, protože mají přiřazeny názvy, které odpovídají přídavným jménům objevujícím se v našem přirozeném jazyce, např. "velké", "střední" nebo "malé". Fuzzy logika. Fuzzy logika je založená na teórii fuzzy množín, čo je zovšeobecnenie klasickej teórie množín. Klasická logika povoľuje iba závery, ktoré sú buď pravdivé, alebo nepravdivé. Vo fuzzy logike môžu byť pravdivostná hodnoty premenných ľubovoľné reálne čísla medzi 0 a 1 vrátane. Preto je funkcia príslušnosti prvku k fuzzy množine definovaná ako krivka, ktorá určuje, ako je každý bod vo vstupnom priestore mapovaný na hodnotu medzi 0 a 1. Vstupný priestor je označovaný ako univerzum diskurzu. Univerzum diskurzu premennej X je spojitý priestor a zvyčajne ho rozdeľujeme do niekoľkých fuzzy množín. Tieto fuzzy množiny sa nazývajú jazykové premenné, pretože majú priradené názvy, ktoré zodpovedajú prídavným menám objavujúcim sa v našom prirodzenom jazyku, napr. "Veľké", "stredné" alebo "malé". Tvorba systému s fuzzy logikou probíhá ve čtyřech krocích: 1. Báze pravidel: Obsahuje množinu IF-THEN pravidel, které zahrnují jazykové proměnné. Tuto bázi navrhli experti v dané oblasti. 2. Fuzzifikace: Používá se k převodu vstupů, tj. přesných čísel, na fuzzy množiny. 3. Interference: Určuje odpovídající stupeň příslušnosti aktuálního vstupu k fuzzy množině s ohledem na každé pravidlo v bázi pravidel a rozhoduje o tom, která pravidla mají být dále použita. 4. Defuzzifikace: Používá se k převedení výsledné fuzzy množiny na reálnou hodnotu. Tvorba systému s fuzzy logikou prebieha v štyroch krokoch: 1. Báza pravidiel: Obsahuje množinu IF-THEN pravidiel, ktoré zahŕňajú jazykové premenné. Túto báze navrhli experti v danej oblasti. 2. Fuzzifikácia: Používa sa k prevodu vstupov, tj. presných čísel, na fuzzy množiny. 3. Interferencia: Určuje zodpovedajúce stupeň príslušnosti aktuálneho vstupu k fuzzy množine vzhľadom na každé pravidlo v báze pravidiel a rozhoduje o tom, ktoré pravidlá majú byť ďalej použité. 4. Defuzzifikácia: Používa sa na prevedenie výslednej fuzzy množiny na reálnu hodnotu. Evoluční výpočty. Evoluční techniky patří do rodiny algoritmů pro globální optimalizaci inspirovaných biologickou evolucí. Z technického hlediska se jedná o stochastické optimalizační algoritmy založené na populacích. V evolučním výpočtu je počáteční populace kandidátských řešení náhodně generována a iterativně aktualizována. Každá nová generace se vytváří stochasticky odstraňováním méně žádaných řešení a přijímáním malých náhodných změn. V biologické terminologii populace podléhá přirozenému výběru (nebo umělé selekci) a mutaci. V důsledku toho se populace postupně vyvíjí, aby se zvýšila vhodnost (fitness) svých řešení. Evoluční výpočetní techniky mohou nalézt optimální řešení pro široké spektrum problémů, což je v informatice činí oblíbeným nástrojem. Evolučné výpočty. Evolučné techniky patria do rodiny algoritmov pre globálnu optimalizáciu inšpirovaných biologickou evolúciou. Z technického hľadiska sa jedná o stochastické optimalizačné algoritmy založené na populáciách. V evolučnom výpočte je počiatočná populácia kandidátskych riešení náhodne generovaná a iteratívne aktualizovaná. Každá nová generácia sa vytvára stochasticky odstraňovaním menej žiadaných riešení a prijímaním malých náhodných zmien. V biologickej terminológii populácia podlieha prirodzenému výberu (alebo umelej selekcii) a mutácii. V dôsledku toho sa populácia postupne vyvíja, aby sa zvýšila vhodnosť (fitness) svojich riešení. Evolučné výpočtové techniky môžu nájsť optimálne riešenie pre široké spektrum problémov, čo ich v informatike robí obľúbeným nástrojom. Evoluční výpočet pracuje v následujících krocích: 1. Otestujte každý chromozom v populaci, abyste zjistili, jak je při řešení problému dobrý a podle toho mu přiřaďte fitness hodnotu. 2. Vyberte dva jedince z aktuální populace. Možnost výběru je úměrná hodnotě fitness každého chromozómů. 3. Aplikujte operátor křížení v závislosti na pravděpodobnosti operace křížení. 4. Aplikujte operátor mutace v závislosti na pravděpodobnosti operace mutace Opakujte kroky 2, 3, 4, dokud nebude vytvořena nová populace. Evolučný výpočet pracuje v nasledujúcich krokoch: 1. Otestujte každý chromozóm v populácii, aby ste zistili, ako je pri riešení problému dobrý a podľa toho mu priraďte fitness hodnotu. 2. Vyberte dva jedince z aktuálnej populácie. Možnosť výberu je úmerná hodnote fitness každého chromozómu. 3. Aplikujte operátor kríženia v závislosti na pravdepodobnosti operácie kríženia. 4. Aplikujte operátor mutácie v závislosti na pravdepodobnosti operácie mutácie Opakujte kroky 2, 3, 4, pokiaľ nebude vytvorená nová populácie. Umělé neuronové sítě. Umělé neuronové sítě jsou výpočetní systémy inspirované biologickými neuronovými sítěmi. Neuronová síť sama o sobě není algoritmem, nýbrž rámcem pro mnoho různých algoritmů z oblasti strojové učení, které společně pracují a zpracovávají složité datové vstupy. Tyto systémy se "učí" vykonávat úkoly na základě předkládaných příkladů, aniž by byly naprogramovány podle specifických pravidel. Umělá neuronová síť obsahuje uzly nazývané umělé neurony, které volně modelují neurony v biologickém mozku. Každé spojení mezi neurony, stejně jako synapse v biologickém mozku, může přenášet signál z jednoho neuronu do druhého. Neuron, který přijímá signál, jej dokáže zpracovat a poté poslat dalším neuronům, s nímž jsou spojeny. Umelé neurónové siete. Umelé neurónové siete sú výpočtové systémy inšpirované biologickými neurónovými sieťami. Neurónová sieť sama o sebe nie je algoritmom, ale rámcom pre mnoho rôznych algoritmov z oblasti strojového učenia, ktoré spoločne pracujú a spracúvajú zložité dátové vstupy. Tieto systémy sa "učia" vykonávať úlohy na základe predkladaných príkladov, bez toho, aby boli naprogramované podľa špecifických pravidiel. Umelá neurónová sieť obsahuje uzly nazývané umelé neuróny, ktoré voľne modelujú neuróny v biologickom mozgu. Každé spojenie medzi neurónmi, rovnako ako synapsie v biologickom mozgu, môže prenášať signál z jedného neurónu do druhého. Neurón, ktorý prijíma signál, ho dokáže spracovať a potom poslať ďalším neurónom, s ktorým sú spojené. V běžných implementacích je signál na spojeních mezi neurony reálné číslo a výstup z každého umělého neuronu je vypočítán podle některé nelineární funkce ze součtu jeho vážených vstupů. Spojení mezi neurony mají přiřazenou váhovou hodnotu, která se přizpůsobuje učením. Neurony jsou typicky uspořádány do vrstev. Signály se pohybují od první vrstvy (vstupní vrstvy) až po poslední vrstvu (výstupní vrstva). Původním cílem umělých neuronových sítí bylo řešit problémy stejným způsobem, jakým by je řešil lidský mozek. V průběhu času se však pozornost přesunula na řešení specifických úkolů, což vedlo k odklonu od biologie. Umělé neuronové sítě byly použity na řešení úloh z oblasti počítačového vidění, rozpoznávání řeči, strojového překladu, extrakci šumu, hraní her a videoher a lékařské diagnostiky atd. V bežných implementáciách je signál na spojeniach medzi neurónmi reálne číslo a výstup z každého umelého neurónu je vypočítaný podľa niektorej nelineárne funkcie zo súčtu jeho vážených vstupov. Spojenie medzi neurónmi majú priradenú váhovú hodnotu, ktorá sa prispôsobuje učením. Neuróny sú typicky usporiadané do vrstiev. Signály sa pohybujú od prvej vrstvy (vstupné vrstvy) až po poslednú vrstvu (výstupná vrstva). Pôvodným cieľom umelých neurónových sietí bolo riešiť problémy rovnakým spôsobom, akým by ich riešil ľudský mozog. V priebehu času sa však pozornosť presunula na riešenie špecifických úloh, čo viedlo k odklonu od biológie. Umelé neurónové siete boli použité na riešenie úloh z oblasti počítačového videnia, rozpoznávanie reči, strojového prekladu, extrakciu šumu, hranie hier a videohier a lekárskej diagnostiky atď. Title: Soft Computing Author: Eva Volná, University of Ostrava, Czech Republic Soft computing became a formal area of study in computer science in the early 1990s. Prof. Lotfi Aliasker Zadeh has defined soft computing as a number of techniques and methods that deal with real-world situations in the same way that people deal with them. In computer science, soft computing (sometimes referred to as Computational Intelligence - CI) is the use of inexact solutions to computationally hard tasks such as the solution of NP-complete problems, for which there is no known algorithm that can compute an exact solution in polynomial time. Soft computing differs from conventional computing in that, unlike hard computing, it is tolerant of imprecision, uncertainty, partial truth, and approximation. In effect the role model for soft computing is the human mind. Soft computing forms the basis of a considerable amount of machine learning techniques. The principal constituents of soft computing are fuzzy logic, evolutionary computation, and neural networks. Generally speaking, soft computing techniques resemble biological processes more closely than traditional techniques, which are largely based on formal logical systems. Soft computing techniques are intended to complement each other. Fuzzy logic. Fuzzy logic is based on the theory of fuzzy sets, which is a generalization of the classical set theory. Classical logic only permits conclusions which are either true or false. In fuzzy logic the truth values of variables may be any real number between 0 and 1 inclusive. Therefore, the membership function is a curve that defines how each point in the input space is mapped to a membership value between 0 and 1. The input space is referred to as the universe of discourse. The universe of discourse X is a continuous space, we usually partition X into several fuzzy sets. These fuzzy sets, which usually carry names that conform to adjectives appearing in our daily linguistic usage, such as "large", "medium" or "small" are called linguistic variables. Creating a system with fuzzy logic contains four steps: 1. Rule base: It contains the set of IF-THEN rules provided by the experts to govern the decision making system, on the basis of linguistic information. 2. Fuzzification: It is used to convert inputs i.e. crisp numbers into fuzzy sets. 3. Inference engine: It determines the matching degree of the current fuzzy input with respect to each rule and decides which rules from the rule base are to be fired according to the input field. 4. Defuzzification: It is used to convert the fuzzy sets obtained by inference engine into a crisp value. Evolutionary computation. In computer science, evolutionary computation is a family of algorithms for global optimization inspired by biological evolution. In technical terms, they are a family of population-based trial and error problem solvers with a metaheuristic or stochastic optimization character. In evolutionary computation, an initial set of candidate solutions is generated and iteratively updated. Each new generation is produced by stochastically removing less desired solutions, and introducing small random changes. In biological terminology, a population of solutions is subjected to natural selection (or artificial selection) and mutation. As a result, the population will gradually evolve to increase in fitness, in this case the chosen fitness function of the algorithm. Evolutionary computation techniques can produce highly optimized solutions in a wide range of problem settings, making them popular in computer science. Evolutionary computation proceeds in the following steps: 1. Test each chromosome to see how good it is at solving the problem at hand and assign a fitness score accordingly. The fitness score is a measure of how good that chromosome is at solving the problem to hand. 2. Select two members from the current population. The chance of being selected is proportional to the chromosomes fitness. Roulette wheel selection is a commonly used method. 3. Dependent on the crossover rate crossover the bits from each chosen chromosome at a randomly chosen point. 4. Step through the chosen chromosomes bits and flip dependent on the mutation rate. Repeat step 2, 3, 4 until a new population has been created. Artificial neural networks. Artificial neural networks are computing systems inspired by the biological neural networks. The neural network itself is not an algorithm, but rather a framework for many different machine learning algorithms to work together and process complex data inputs. Such systems "learn" to perform tasks by considering examples, generally without being programmed with any task-specific rules. An artificial neural network is based on a collection of connected units or nodes called artificial neurons, which loosely model the neurons in a biological brain. Each connection, like the synapses in a biological brain, can transmit a signal from one artificial neuron to another. An artificial neuron that receives a signal can process it and then signal additional artificial neurons connected to it. In common implementations, the signal at a connection between artificial neurons are a real number, and the output of each artificial neuron is computed by some non-linear function of the sum of its inputs. Artificial neurons and edges typically have a weight that adjusts as learning proceeds. Typically, artificial neurons are aggregated into layers. Signals travel from the first layer (the input layer), to the last layer (the output layer). The original goal of the ANN approach was to solve problems in the same way that a human brain would. However, over time, attention moved to performing specific tasks, leading to deviations from biology. Artificial neural networks have been used on a variety of tasks, including computer vision, speech recognition, machine translation, noise filtering, playing board and video games and medical diagnosis etc.