Лекция: Генетические алгоритмы. Определение. Схема классического генетического алгоритма. Области применения классических генетических алгоритмов.

Г.А. – это методы поиска решений сложных задач, используя принципы биолог.эволюции (Изменчивость, отбор, наследственность).

Первоначально случайным образом генерируется популяция решений задачи. Далее в ходе решения наименее подходящие решения устраняются наиболее вероятные сохраняются скрещиваются, и дают потомство еще более подходящие решения. И так до тех пор пока не будет достигнуто оптимальное или близкое к нему решение.

Рассмотрим схему Г.А.:

Каждый этап имеет множество вариантов реализации. Рассмотрим классический Г.А.

Пример: Дана функция.. Наитии максимум. Для эффективной работы Г.А. возможные решение кодируется двоичными строками – хромосомами, а каждый их отдельный бит – ген. Теперь мы ищем оптимальное решение не во множестве {0,1,2…15}, а во множестве {0000, 0001, 0010…1111}.

1. Инициализация. Сл. образом формируется нач. популяция решений. Пример: пусть количество особей в популяции m=b. {0010, 0101, 0111, 1001, 1100, 1110} {2, 5, 7, 9, 12, 14}.

2. Оценка. Для каждой особи текущей популяции вычисляется ее приспособляемость (как она справляется с решением задач). Для этого используется функция приспособляемости (оценки). Для примера фун. б/т. Чем больше функция те более приспосабливаются особи. Для примера 0010 (2) — 4, 0101 (5) — 25, 0111 (7) — 49, 1001 (9) — 81, 1100 (12) — 144, 1110 (14) – 196.

3. Отбор. Из текущей ситуации выбирают наиболее приспосабливаемые особи. Обычно для этого используется метод рулетки. Ставим в соответствие каждой особи сектор рулетки так, чтобы его ширина была проп-на приспос-ти особи. Запускаем рулетку m раз. Тем самым выбираем m особей для участия в созд-ии следующей популяции. При этом некоторые особи могут выбраны несколько раз: пр: {0111, 1001, 1100, 1100, 1110, 1110}.

4. Скрещивание. Отбор особи происходит путем произольного разбиения на пары, и далее скрещиваются. Для двух особей выбирается точка скрещивания и особи обмениваются правыми частями. Пр.0000|00 000011

1111|11 111100 При этом не все пары подвергаются скрещиванию. Это происходит с некоторой вероятностью 0,6≤ρ≤1. Если особи скрещиваются, то в следующую популяцию переходят их потомки, иначе переходят сами особи.

5. Мутация. После скрещивания особи могут мутировать. Для каждой особи просматриваются ее виды и инвертируются с вероятностью 0≤ρмут≤0,001. И т.д. процесс повторяется пока не будет достигнуто условие завершения алгоритма:

· Достигнуто мах кол-во поколений (максимальное время работы алгоритма)

· Популяция прекращает улучшаться (все особи становятся примерно одинаковыми).

Применение:

1. Задачи оптимизации (транспортная задача)

2. Для составления расписаний

3. Создание дизайна

4. Создание компьютерных программ (генетическое програмирование)

Обучение нейронных сетей.

 

39,Нечеткая логика

В клас. Логике утверждения м.б. только «И», либо»Л». В нечеткой л-ке утверждения м.б. и «И» и «Л». «И» с некоторой степенью. Нечет л-ка более четко отражает мир. Для утверждения «И» вводится ф-я принадлежности(истинности) она прнадлеж [0, 1]. 0-утверждение точно «Л», 1-точно «И», 0,7-«И» на 70%. Правила вычисления сложных выск-й: выск-е делится на простые и составные(и, или, не). Пусть m(A),m(B)-«И» выс-е А и В, тогда: 1)m(not(A))=1-m(A); 2)m(AandB)=min{m(A),m(B)}; 3)m(AorB)=max{m(A),m(B)}. Области применения:1)управление; 2)распознавание;3)прогнозирование. Пример системы упр. На основе неч. Логики(упр. Комнат. Кондиционероом)Даны правила: 1)если темпер низкая, то скорость вращения низкая

2)темпер средн-v cредняя 3)если темпер высокая – V высокая. От датчика температуры нужно опр ско-ть вращения. Алгоритм: 0)вначале строим функции истинности для высказываний tср, низ, выс и Vср, низк, высок. 1)для левых частей правил вычисл их истинность. Пусть датчик показывает t=22. Низк m t (22)=0, средн m t (22)=0,7; высок m t (22)=3. 2)С помощью получ зн-й изменяются функции принадлежности для правых частей(сжим с этим коэф)

3)получим ф-ии принадлежности объедин в одну. берем макс по всем точкам. 4) по этой общей ф-ии опр искомую скорость(центр тяж)v=1150

 

40. Программное обеспечение ЭВМ (ПО ЭВМ): понятие, общая классификация. Системное программное обеспечение ЭВМ. Прикладное программное обеспечение ЭВМ.

ПО ЭВМ – совокупность всех программ, обеспечивающих норм функционирование компьютера и решение с его помощью разнообразных задач.

Компьютер представляет собой единство аппаратного обеспечения – hardware, и программного обеспечения – software(freeware — бесплатное, shareware-условно бесплатное [временно рабочие или с ограниченными функциями], trial-демоверсии, платные – покупаются как продукт)

Рассмотрим классификацию ПО ЭВМ по назначению:

Программное обеспечение условно можно разделить на 3 класса: системное ПО, прикладное ПО и инструментальное ПО.

1. Системное программное обеспечение, в свою очередь, состоит из базового ПО и сервисного ПО.

Базовое ПО — поставляется вместе с компьютером и обеспечивает его работоспособность. В состав базового ПО входит операционная система (ОС), операционная оболочка (ОО) и сетевые программные средства (СПС).

ОС –совокупность программ, которые частично автоматизируют управление работой компьютера.

Интерфейс – способ взаимодействия.

Пользовательский интерфейс – это средство взаимодействия пользователя с программой (типы: командный – с клавиатуры вводятся команды, WIMP – выбор из меню или графических знаков, SILK – речевые команды и смысловые связи)

ОС выполняет роль посредника между: человек-компьютер (пользовательский интерфейс); между программами (программный интерфейс); между программами и аппаратурой (программно-аппаратный интерфейс).

Операционная система предназначена:

— Управление ресурсами компьютера,

— Управление работой внешних устройств,

— Координация работы всех частей компьютера,

— Организация диалога с пользователем,

— Управление исполнением программ и обеспечение их взаимодействия с аппаратурой.

Блоки ОС:

1. Ядро операционной системы — резидентная часть – BiOS, включает модули:

А. BiOS – система хранится в ПЗУ и запускается при включении компьютера

Б. Модуль начальной загрузки – короткая программа, расположенная в первом загрузочном секторе системного диска

В. Системные модули ОС – располагаются в отдельном месте системного диска (*.sys)

2. Драйверы внешних устройств – это программа, управляющая работой внешнего устройства, преобразуя данные на входе и выходе (каждое внешнее устройство имеет свой драйвер).

3. Командный процессор — интерпретатор команд (команды пользователя преобразует в двоичные коды, исполнение файла автозапуска, для каждой оси существует свой набор команд: а. внутренние команды [вкл/выкл, просмотр и т.п.], б. внешние команды — .exe, .com)

В настоящее время разработано большое количество ОС, различающихся по возможностям их функционирования: в режимах: одно- и многопользовательских, одно- и многозадачных, поддерживающих сетевые режимы и др. Широкое применение нашли следующие ОС: Windows, Linux, Mac OS, NetWare, OS/2, Solaris, QNX, MS DOS и др.

Оболочка ОС предназначена для комфортного общения пользователя с ЭВМ.

ОО обеспечивает: наглядное представление каталогов и информации о файлах, удобное перемещение по файловым системам и доступ к файлам, удобство манипуляции (копирование, перемещение), выбор команд из меню или с помощью функциональных клавиш.

Она снимает проблему управления компьютером с помощью набора команд в командной строке и их запуска на исполнение. Оболочка ОС реализует текстовый или/и графический интерфейс. Например, в ОС MS DOS в качестве такой надстройки выступает программа-оболочка Norton Commander, реализующая текстовый интерфейс в виде двух таблиц с директориями файловой системы, а в ОС Windows (и Mac OS) интерфейс оболочки — графический; имеется также текстовый интерфейс, реализуемый программой Windows Commander.

Сетевая ОС обеспечивает работу компьютера в сети и поддерживает все сетевые службы — электронную почту, обмен файлами, доступ к сайтам, общение между клиентами через Интернет и пр.

Сервисное ПО расширяет возможности компьютера и может приобретаться за отдельную плату или в последующем поставляться через Интернет (программы диагностики работоспособности, антивирусы, архиваторы, программы обслуживания диска и т.п.).

В настоящее время такие известные операционные системы как Windows XP, MAC OS и некоторые другие включают в себя все вышеперечисленные компоненты системного ПО, являясь по существу комплексным системным ПО.

2. Прикладное программное обеспечение предназначено для решения различных задач из конкретных предметных областей.

ПО общего назначения обычно комплектуется в пакетном варианте. Например, для ОС Windows имеется пакет прикладных программ Microsoft Office, включающий программные средства для создания текстовых документов (Word), электронных таблиц (Excel), презентаций (Power Point), публикаций (Publisher), базы данных (Access), для подготовки и редактирования Web-документов (FrontPage).

В этот пакет также входит ряд дополнительных программных средств: Picture Manager для просмотра, систематизации и редактирования графики, Document Imaging для просмотра, чтения и распознавания текста в графических документах и факсах, Document Scanning для сканирования многостраничных документов и распознавания текста в графических документах, файл библиотеки картинок и др.

ПО мультимедиа предназначено для создания и использования двумерной и трёхмерной графики, анимации, аудио и видео файлов. Представителями этих ПО являются широко известные программные комплексы Adobe Photoshop для создания и редактирования двумерной графики, 3D Studio Max для трёхмерного моделирования и проектирования, Macromedia Flash для анимации и мультипликации. Для обработки и редактирования звука используются популярные программы Nero, Audio Editor Gold, для воспроизведения звука и видео Windows Media Player, QuickTime Player и др.

Проблемно-ориентированное ПО пожалуй самый распространённый подкласс прикладных программных средств. Сюда относятся пакеты программ для управления производством, ведения бухгалтерского учёта, управления кадрами, управления материальными ценностями и др.

Большой спектр прикладных программ разработан в качестве информационных систем (см. «Информатика и информация»), куда относятся и информационно-поисковые, и издательские и прочие системы.

еще рефераты
Еще работы по информатике