Математические методы решения задачи расчета химического равновесия. Структура программного средства. Схема отношений базы данных химических элементов и соединений. Программная реализация Генетического Алгоритма для расчета химического равновесия.
Аннотация к работе
Рассмотрена математическая модель метода решения задачи расчета химического равновесия, а также приведена постановка задачи разработки программного средства расчета с использованием генетического алгоритма. При исследовании таких задач в модель включают компоненты «с большим запасом», что повышает размерность минимизационной задачи, представленной зависимостями (2,3). В системах Mathematica 4.1/4.2 были следующие две функции для поиска глобального максимума и минимума аналитически заданной функции: · CONSTRAINEDMAX[f, {inequalities}, {x, y, ...}] - ищет глобальный максимум функции f в области, определяемой неравенствами inequalities. Особь - объект реального мира, входящий в популяцию и представляемый хромосомами с закодированными в них параметрами задачи, т.е. особь представляет собой решение из пространства поиска [6,8,9]. · оценка приспособленности хромосом в популяции сводится к расчету функции приспособленности для каждой хромосомы этой популяции: чем больше значение этой функции, тем выше «качество» хромосомы;В качестве основного фактора, определяющего трудоемкость и длительность разработки ПП, принимается размер исходного текста программы. G и Т определяются по формулам (28-31): , (28) где n-количество тысяч строк исходного текста программы. В разработке данного программного продукта принимали участие постановщик задачи и программист. Текущие затраты (С) включают затраты на постановку задачи, разработку алгоритмов программ, а также затраты, связанные с содержанием и эксплуатацией ВТ, используемой при разработке ПП, и рассчитываются по следующей формуле (34): С = Зпр Нз Змаш Зн (35) где Зпр - затраты на заработную плату проектировщиков и программистов: Зпр = 20 400 (руб.) (36) Змаш-затраты, связанные с использованием машинного времени на разработку и отладку программы: Змаш = Тмаш * Смаш (38) где Тмаш - машинное время на разработку и отладку программы: Тмаш = 110 (час); (39)Финансовый план содержит обоснование экономической эффективности затрат, произведенных в связи с разработкой и реализацией ПП. Так как принято решение осуществить разработку ПП за счет собственных средств предприятия-разработчика без привлечения коммерческого кредита, срок окупаемости ПП (69-71) определяется сроком окупаемости инвестиционных вложений. Но, несмотря на это, оператор, работающий с ПК, испытывает на себе различные негативные факторы, связанные с работой за компьютером и помещением, в котором он находится. При работе с компьютером человек подвергается воздействию ряда опасных и вредных производственных факторов: электромагнитных полей (диапазон радиочастот: ВЧ, УВЧ и СВЧ), инфракрасного и ионизирующего излучений, шума и вибрации, электричества и др. В противном случае у персонала отмечаются значительное напряжение зрительного аппарата с появлением жалоб на неудовлетворенность работой, головные боли, раздражительность, нарушение сна, усталость и болезненные ощущения в глазах, в пояснице, в области шеи и руках.В ходе выполнения дипломной работы было спроектировано и реализовано программное средство вычисление химического равновесия с применением генетического алгоритма.Данное игровое приложение обладает следующими требованиями к техническому обеспечению: Для сервера: · операционная система Windows XP и выше; · 32 или 64 разрядный процессор семейства Intel Pentium с тактовой частотой 1,0 Ghz или выше; · 32 или 64 разрядный процессор семейства Intel Pentium с тактовой частотой 1,0 Ghz или выше; При входе в органайзер пользователь видит следующее игровое окно (рис. Управление игровым персонажем происходит с помощью клавиатуры (рис.П.В.1 Общие сведения о программе Данное игровое приложение обладает следующими требованиями к техническому обеспечению: Для сервера: · операционная система Windows XP и выше; · 32 или 64 разрядный процессор семейства Intel Pentium с тактовой частотой 1,0 Ghz или выше; Назначение программного средства заключается в реализации и предоставлении графического интерфейса игрового процесса. Программа состоит из запускаемого файла и файлов ресурсов, содержащих текстуры, модели и шейдеров игрового приложения.
План
5.4 Производственный план5.6 Финансовый план
Введение
Протекание реальных процессов в физико-химических системах зависит от большого числа компонентов, их температуры и давления. Они включают в себя многостадийные химические превращения, фазовые переходы, явления переноса массы и энергии. При этом справедливо утверждение о том, что химическая реакция способна нарушить термодинамическое равновесие [1] - состояние системы, при котором остаются неизменными по времени макроскопические величины (температура, давление, объем, энтропия) в условиях изолированности от окружающей среды. Таким образом, описываемые процессы в некоторой мере характеризуются неравновесностью. Ежедневно в окружающем нас мире реализуется большое количество примеров таких сложных процессов: от процессов сгорания топлива в двигателе внутреннего сгорания автомобиля, до реакций, протекающих в ядерных реакторах.
Для того чтобы определить как изменятся физико-химические параметры системы может быть применена химическая термодинамика [2]. Универсальность положений термодинамики и сравнительная простота основанных на них моделей делают термодинамический анализ удобным средством предметного моделирования, в основе которого лежат теория подобия и анализ размерностей. Необходимым условием такого моделирования является пропорциональность физических величин, характеризующих реальную систему, соответственным величинам, реализуемым в модели. Наличие такой пропорциональности позволяет производить перерасчет экспериментальных результатов, получаемых для модели, на реальную систему путем умножения каждой из определяемых величин на постоянный для всех величин данной размерности множитель - коэффициент подобия.
При сведении задач кинетики к задачам термодинамики удается, с одной стороны, упростить описания изучаемых объектов, а с другой - сделать эти описания более разносторонними [1].
Ключевым вопросом построения моделей химических систем является применимость принципа химического равновесия [1-4]. Под химическим равновесием понимается состояние химической системы, в котором обратимо протекает одна или несколько химических реакций, причем скорости в каждой паре прямая - обратная реакция равны между собой. Для систем, находящихся в химическом равновесии температура и другие параметры системы не изменяются во времени.
Термодинамика, в свою очередь, может быть определена как наука о равновесиях, а использование ее положений корректно только в случаях, когда справедливы предположения о равновесности изучаемых процессов и состояний. Оценка корректности предположений о соблюдении этого принципа обычно является нетривиальной [4].
Математически проблема расчета равновесного состава формулируется как задача условной нелинейной многопараметрической оптимизации (математического программирования). Ее решение традиционными регулярными [3] и стохастическими [5] методами сопряжено с рядом сложностей. В результате возникают жесткие ограничения как на число разрешаемых в модели компонентов (веществ), так и на качество начального приближения к искомому равновесному составу [4]. Для преодоления названных ограничений в последнее время интенсивно развиваются эволюционные подходы к решению оптимизационных задач, адаптирующиеся к специфике конкретных задач на базе гибкого эволюционирующего сочетания преимуществ регулярных [3] и стохастических [5] методик. Одним из известных эволюционных подходов является генетический алгоритм (ГА).
Генетические алгоритмы предназначены для решения задач оптимизации и моделирования путем случайного подбора искомых параметров. В его основе лежит метод случайного поиска, а также закономерности, проявляющиеся в биосистемах. Поэтому генетический алгоритм относят к классу эволюционных вычислений. Данные эвристические методы показали хорошую сходимость для задач оптимизации большой размерности, трудноразрешимых традиционными методами [6].
Изложенные выше факты наглядно свидетельствуют об актуальности выбранной тематики. Данная работа представляет собой программно-алгоритмическую основу программного средства расчета химического равновесия и описывает методологию выполнения параметрической оптимизации с использованием генетического алгоритма.
Работа структурно состоит из трех разделов, введения, заключения, ссылок на использованные источники и приложений. В первом разделе приведены результаты оригинального обзора методов и программных средств, которые могут быть применены для решения задачи. Рассмотрена математическая модель метода решения задачи расчета химического равновесия, а также приведена постановка задачи разработки программного средства расчета с использованием генетического алгоритма.
Во втором разделе рассмотрен классический генетический алгоритм и определена стратегия его применения в контексте рассматриваемой задачи, а также приведено описание основных алгоритмов разрабатываемого программного средства.
В третьем разделе рассмотрена архитектура проектируемого программного средства, проведено обоснование средств разработки и описана выбранная схема отношений базы данных.
1. Аналитический обзор методов и средств расчета химического равновесия
1.1 Математическая модель задачи расчета химического равновесия
Если реагирующие газовые среды рассматривать как динамические системы, практически интересны их равновесные или стационарные состояния. Простейшей моделью здесь служит идеальный газ, внутренняя энергия которого определяется исключительно кинетической энергией его частиц. Между этими частицами имеют место только упругие столкновения [1].
Под компонентами в термодинамике обычно понимают входящие в реагирующую смесь вещества независимо от того, в скольких фазах они присутствуют. В данной работе каждая из фаз одного и того же вещества считается отдельным компонентом. Так как при расчетах равновесий требуется найти количество молей каждого вещества в каждой из фаз, причем с различными характеристиками, поэтому естественно считать эти количества самостоятельными переменными задачи. Каждый компонент многокомпонентной идеальной газовой смеси ведет себя так, как будто он один занимает весь объем, в котором расположена смесь.
Химический потенциал j-го компонента идеального газа определяется формулой (1)
, (1) где - универсальная газовая постоянная;
- абсолютная температура;
- общее давление смеси;
;
- количества молей j-го компонента в смеси в целом.
Формула (1) справедлива для любых идеальных термодинамических систем, и ее выполнимость может служить определением последних.
Поскольку устойчивые равновесные состояния характеризуются минимальной энергией, то имеет место известная модель Гиббса - Гельмгольца (2,3) по минимизации функционала
, (2) при ограничениях, отражающих сохранение количества вещества (поэлементно)
, (3) где - матрица размерностью содержаний элементов в компонентах системы;
- вектор количества молей i-го элемента.
Особенность такой модели в том, что исходными данными служит вектор параметров, характеризующих физико-химические свойства всех веществ в системе - вектор с характеристиками вещества и . Выбор ведущих веществ и реакций не слишком сложен для изученных процессов и существенно проблематичен для вновь исследуемых систем. Однако именно такие процессы представляются актуальным объектом термодинамического анализа. При исследовании таких задач в модель включают компоненты «с большим запасом», что повышает размерность минимизационной задачи, представленной зависимостями (2,3). Следует отметить, что наряду с методами прямой условной минимизации термохимического потенциала системы существуют методы констант равновесия [2,3], основанные на составлении системы уравнений частичного равновесия - между отдельными веществами. Эти методы, однако, оказываются более чувствительными к выбору начального приближения (причем уже на уровне базовых веществ и реакций), и их практическое применение сильно затрудняется с ростом размерности системы.
Запишем модель в удобной для минимизации постановке, зафиксировав температуру Т, давление Р и исходный состав вещества
, (4)
, (5)
, (6) где - массовая доля атомов i-го сорта в компоненте j;
- вектор масс компонентов;
- минимальная масса j-ого компонента;
- вектор масс атомов сорта;
и - соответственно молярная масса j-ого компонента и его химический потенциал;
M и P - общие масса и давление соответственно.
В первом приближении [2,3]: , (7)
где , , - соответственно энтальпия образования, теплоемкость при постоянном давлении и энтропия j-ого компонента при T = 298 K.
Энтальпия образования (иначе, теплосодержание) представляет собой термодинамический потенциал, характеризующий состояние системы в термодинамическом равновесии при выборе в качестве независимых переменных давления, энтропии и числа частиц.
Для решения задачи (4-7) обычно применяются регулярные (метод линеаризации, метод линейного программирования и метод квадратичной аппроксимации) и стохастические (метод Монте-Карло) методы. Рассмотрим подробнее эти методы для определения их достоинств и недостатков.
1.2 Математические методы решения задачи расчета химического равновесия
1.2.1 Метод множителей Лагранжа
Метод множителей Лагранжа [3] заключается в нахождении условного экстремума функции f(x), относительно m ограничений ?i(x), где i=1..m. Он состоит из нескольких этапов: · составление функции Лагранжа в виде линейной комбинации функции f и функций ?i , взятых с коэффициентами, называемыми множителями Лагранжа (?i);
· составление системы из n m уравнений, путем приравнивания частных производных функции Лагранжа по xj и ?i;
· если полученная система имеет решение относительно параметров xj‘ и ?i‘, тогда точка x’ может являться условным экстремумом, т.е. решением исходной задачи.
Будем рассматривать газовую смесь M составляющих с потенциалом
; (8) и условиями
, (9)
; (10)
Минимизация G при этих условиях, согласно уравнениям (8-10) эквивалентна отысканию безусловного экстремума функции
(11) где и - неопределенные множители Лагранжа.
1.2.2 Метод линеаризации
Линеаризация является одним из методов аппроксимации нелинейных систем до линейных систем, в некотором смысле эквивалентных исходным нелинейным. Необходимые условия экстремума (i=1,2,…,M) и приводят к системе M 1 уравнений
, , (12) где
.
Из последнего уравнения в этой системе (8-12) при учете (9) следует равенство , так что это уравнение впредь можно опустить.
Равновесный состав, следовательно, определяется следующей системой M m l уравнений (13-15)
; (13)
; (14)
, (15) относительно M m l неизвестных , и , при этом i = 1, 2 ,…, M, j=1,2,…,m.
Эта система может быть линеаризована обычным путем: разложением функций и в ряд Тейлора вблизи некоторых начальных значений и с последующим использованием для аппроксимации только линейных членов (метод Ньютона): ; , (16) где ;
;
и - некоторые значения неизвестных, которые определяются из системы линейных уравнений, получающейся из (13-15) после подстановки в нее выражений (16) и замены ni, n на и .
Найденные значения и используются в качестве нового начального приближения, находятся и и т.д., пока не будет достигнут окончательный результат (если процесс сходится для данной задачи).
1.2.3 Метод линейного программирования
Линейное программирование представляет собой класс методов решения задач на поиск экстремумов на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.
Рассматриваемая задача есть не что иное, как задача нелинейного программирования при наличии линейных ограничений - уравнений материального баланса. Однако может быть непосредственно использован метод линейного программирования для отыскания решений исходной системы уравнений равновесного состава [3]. Для этого достаточно представить функцию G в виде: ; (17) и аппроксимировать далее каждый член вида или кусочно линейной функцией на отрезке изменения переменных или . Далее задача сводится к задаче линейного программирования.
Данный метод (17) обладает при достаточной простоте алгоритма одним важным преимуществом: для его сходимости неважно, сколь близкими к нулю могут оказаться значения [3].
1.2.4 Метод Монте-Карло
Методы Монте-Карло - это общее название группы численных методов, которые основаны на получении большого числа реализации случайного процесса, который формулируется таким образом, чтобы его вероятностные характеристики совпадали с аналогичными величинами решаемой задачи.
Зададим функцию . Выбираем область поиска решения задачи, как , после чего: · производим случайные броски, т.е. выбираем значения , для каждой переменной по формуле (18)
, (18) где .
· сравниваем значения функции
·
(19) и если неравенство (19) выполняется, то новым значением минимума принимаем z(m), иначе - z(m 1);
· процесс случайных бросков продолжается до достижения заданной точности ?, при это число случайных бросков удовлетворяет условию
, (20) где , .
Данный метод (18-20) показал высокую эффективность в сложных задачах, когда применение других методов затруднительно или неэффективно изза большого количества параметров и сложности вычисления производной функции.
Описанные выше методы обладают недостатками, присущими аналитическим, переборным и стохастическим методам - повышение количества компонентов расчета для традиционных методов является узким местом в их реализации и требует введения жестких ограничений на качество начального приближения к искомому равновесному составу [4].
В отличие от представленных регулярных методов эволюционные алгоритмы позволяют осуществлять поиск решения исходя не из единственной точки, а из их некоторой популяции. Несомненным преимуществом эволюционных стратегий также является то, что в процессе оптимизации они используют только целевую функцию, а не ее производные, либо иную дополнительную информацию [6].
1.3 Средства автоматизации расчета задачи химического равновесия
1.3.1 Реализация методов оптимизации в стандартных пакетах прикладной математики
Пакеты символьных вычислений обеспечивают автоматическое выполнение многих аналитических выкладок. В иностранной литературе этот класс пакетов обозначается аббревиатурой CAS - COMPUTER ALGEBRA SYSTEMS. Среди них можно назвать такие пакеты, как MAPLE, MATHEMATICA, MACSYMA, DERIVE,AXIOM.
В Maple для линейной оптимизации используется библиотека simplex, которая содержит команды для решения задач линейной оптимизации при помощи симплекс-метода. Перед обращением к командам пакета его нужно подгрузить или использовать вызов команды с префиксом пакета
В системах Mathematica 4.1/4.2 были следующие две функции для поиска глобального максимума и минимума аналитически заданной функции: · CONSTRAINEDMAX[f, {inequalities}, {x, y, ...}] - ищет глобальный максимум функции f в области, определяемой неравенствами inequalities. Полагается, что все переменные x, y, ... неотрицательны.
· CONSTRAINEDMIN[f, {inequalities}, {x, y,...}] - ищет глобальный минимум функции f в области, определяемой неравенствами inequalities. Полагается, что все переменные x, y, ... неотрицательны.
После имени функции указывается максимизируемая целевая функция, затем указываются все ограничения и, наконец, список искомых переменных. Таким образом, пакет Mathematica можно использовать для решения типовых задач линейного программирования.
Maplesoft продает как студенческую, так и профессиональные версии Maple, с существенной разницей в цене (99 $ и 1995 $, соответственно).
Недавние студенческие версии (начиная с шестой) не имели вычислительных ограничений, но поставлялись с меньшим объемом печатной документации. Так же различаются студенческая и профессиональная версии пакета Mathematica .
1.3.2 Chemical Equilibrium Calculation
Chemical Equilibrium Calculation - это наиболее совершенная программа расчета равновесий «Chemical Equilibrium Calculation» (СЕС) [7], доступная в онлайн-режиме, которая позволяет бесплатно рассчитывать состав некоторых систем. Доступ к интересующим пользователя базам исходных термохимических данных и расчет многокомпонентных практически интересных составов требует оформления дорогостоящего договора с разработчиком.
В качестве набора исследуемых компонентов нами были отобраны: C - углерод, H - водород, H2 - водород, CH4 - метан, C2H2 - ацетилен. Столь малый набор компонентов связан с ограничениями общедоступной версии CEC. Инициализация параметров эксперимента представлена ниже (рис. 1).
Рисунок 1 - Пример заполнения «CEC» начальными данными
Как видно на рисунке 1, эксперимент проводился при T=300 C и давлении P=1 ат. Результаты работы «СЕС» представлены на рисунке 2.
Рисунок 2 - Результаты работы программы CEC
Нетрудно убедиться, что добавление в систему таких веществ как C8H18 (октан - простейшая модель бензина) переводит расчет состава при помощи СЕС в разряд коммерческих.
Поэтому целью данной разработки ставится создания аналогичного СЕС продукта, обладающего близкой функциональностью, но существенно открытого в отношении базы исходных термохимических данных и не имеющего жестких ограничений на номенклатуру разрешаемых в расчете компонентов. В качестве метода решения задачи расчета химического равновесия предполагается использовать биоинспирированный подход на основе генетического алгоритма, в основе которого находится сочетание на уровне вычислительного алгоритма достоинств регулярного и стохастического подходов.
1.4 Постановка задачи на разработку программного средства расчета химического равновесия
Целью данной работы является разработка программного средство для расчета химического равновесия на основе параметрической оптимизации при помощи генетического алгоритма.
В соответствии с техническим заданием (приложение А), программное средство должно реализовывать функцию нахождения равновесного состояния системы, состоящей из химических компонент (газов) при заданных пользователем начальных данных. Входными данными расчета выступают: температура, давление, начальные массы компонентов. Выходными данными расчета являются: рассчитанные массы компонентов, представленные в виде графиков и текстовой информации.
Выполнение расчета необходимо производить с использованием генетического алгоритма, а в качестве целевой функции использовать математическую модель Гиббса-Гельмгольца (4-7), при этом программное средство должно реализовывать графический интерфейс и предоставлять возможность доступа к результатам расчета по сети.
В следующих разделах работы будут рассмотрены алгоритмическое конструирование и программная реализация разрабатываемого программного средства.
2. Алгоритмическое конструирование программного средства расчета химического равновесия
2.1 Классический генетический алгоритм
Генетический алгоритм (в дальнейшем, ГА) - эвристический алгоритм поиска, использующий метод случайного поиска. Основным недостатком случайного поиска является то, что заранее неизвестно, сколько понадобится времени для решения задачи. Для того, чтобы избежать существенных временных расходов при решении поставленной задачи оптимизации, применяются методы, открытые при изучении эволюции и происхождения видов.
Перед рассмотрением собственно механизма реализации ГА, обратимся к рассмотрению основных понятий общих для всех эволюционных стратегий, которые будут использованы нами далее.
Популяция - конечное множество особей.
Особь - объект реального мира, входящий в популяцию и представляемый хромосомами с закодированными в них параметрами задачи, т.е. особь представляет собой решение из пространства поиска [6,8,9].
Хромосомы - упорядоченные последовательности генов, где ген - это атомарный элемент генотипа, в частности, хромосомы [6,8,9].
Генотип - это набор хромосом некоторой особи [6].
Фенотип - это набор значений, соответствующих некоторому генотипу, т.е. декодированная структура или множество параметров задачи [6].
Как известно, в процессе эволюции выживают наиболее приспособленные особи и, следовательно, приносят больше потомства, чем плохо приспособленные особи. При этом благодаря передаче генетической информации потомки наследуют от родителей основные их качества (гены). Это приводит к тому, что приспособленность популяции возрастает, позволяя ей лучше выживать в изменяющихся условиях. Оценка уровня приспособленности особей производится с использованием функции приспособленности.
Функция приспособленности представляет собой меру приспособленности каждой особи в популяции. Эта функция выбирает наиболее приспособленные особи в соответствии с эволюционным принципом «выживает сильнейший» [6].
Каждая новая популяция в ГА называется поколением. В каждом следующем поколении мы можем наблюдать возникновение совершенно новых решений исходной задачи. Среди них будут как плохие, так и хорошие, но благодаря «естественному» отбору число хороших решений будет возрастать [6,8,9]. Блок-схема классического ГА представлен на рис.3.
Рассмотрим суть представленных этапов генетического алгоритма: · инициализация популяции хромосом заключается в формировании исходной популяции с использованием случайного выбора заданного количества хромосом (особей), представляемых двоичными кортежами фиксированной длинны;
· оценка приспособленности хромосом в популяции сводится к расчету функции приспособленности для каждой хромосомы этой популяции: чем больше значение этой функции, тем выше «качество» хромосомы;
· проверка условия завершения в нашем случае будет заключаться в проверке факта достижения искомого значения с заданной точностью, либо в проверке существенности улучшения, принесенного очередным этапом селекции;
· селекция хромосом заключается в выборе тех хромосом, которые будут участвовать в создании потомков для следующей популяции;
· применение генетических операторов (скрещивания и мутации) к хромосомам особей, отобранным с помощью селекции, позволяет сформировать новую популяцию;
· в классическом ГА особи, полученные на предыдущем шаге, включаются в состав новой популяции, полностью замещая собой родительскую популяцию той же численности;
· выбор «наилучшей» хромосомы происходит в случае выполнения условия остановки алгоритма среди особей последней популяции таким образом, чтобы выбрать особь с максимальным значением функции приспособленности.
Перейдем к рассмотрению конкретных вопросов реализации классического ГА, связанных с задачей расчета химического равновесия. генетический алгоритм химический равновесие
2.2 Кодирование входных данных и представление особей
Для представления объектов реального мира в виде особей популяции классического ГА применяются методы кодирования. Широко распространены двоичное и логарифмическое кодирование. Первое является более простым в реализации, однако при большом числе кодируемых данных может приводить к значительному размеру векторов, представляющих хромосомы особей. Второе, позволяет существенно сократить запись хромосом, однако, является более сложным для кодирования/декодирования и требует выполнения приближения.
В качестве входных данных задачи оптимизации выступают температура, давление и начальные массы компонентов. Так как число компонентов может быть значительным, то имеет смысл использовать логарифмическое кодирование. Его суть заключается в использовании следующей зависимости
, (21) где ? и ? принимают целые значения из интервала [0,1];
[bin]10 - десятичное значение двоичной последовательности bin.
Таким образом, каждый признак записывается в виде одного вещественного числа, которое может быть легко представлено в двоичной форме (21).
Алгоритм выполнения кодирования (декодирования) значений масс компонентов задачи представлен на рис. 4.
Значения передаются в процедуру кодирования/декодирования по ссылке, поэтому их значения сохраняются после того, как функция заканчивает свою работу. В качестве возвращаемого значения выступает флаг Select, который определяет задание, выполненное функций (кодирование или декодирование).
Константа CODING определяет значение, соответствующее выбору функции кодирования. Параметр Binary представляет бинарный массив значений, а параметр Number - вещественное число.
Выбранный алгоритм предполагает необходимость представления вещественного числа в двоичной форме. Воспользуемся известным способом представления вещественных чисел, применяемых в ЭВМ, а именно в виде с плавающей запятой. Этот способ, как известно, опирается на нормализованную запись действительных чисел с использованием мантиссы и порядка [10].
Рисунок 4 - Кодирование/декодирование массы
Алгоритм представления числа с плавающей запятой состоит из следующей последовательности шагов [10]: · перевести число из десятичной системы счисления в двоичную;
· представить двоичное число в нормализованной экспоненциальной форме;
· рассчитать смещенный порядок числа;
· разместить знак, порядок и мантиссу в соответствующие разряды сетки двоичного представления вещественного числа.
Вещественное значение, представляющее массу входного компонента, соответствует одной хромосоме. Каждая особь имеет такое количество хромосом, сколько входных компонент для расчета задано.
2.3 Расчет функции приспособленности
В рассматриваемой задаче необходимо обеспечить минимизацию химического потенциала G, поэтому функцию приспособленности (22) представим в виде
, (22) где x - особь, для которой вычисляется значение функции приспособленности;
G(x) - химический потенциал особи x, полученный на основании зависимостей (4-7).
Очевидно, что вектор молярных масс компонентов, а также температура и давление (в соответствии с математической постановкой) являются неизменными входе эксперимента, а общая масса может быть легко вычислена.
Важным является соблюдение ограничений по массе для каждой из компонент. Для этого, определяется входной вектор минимальных масс, каждого компонента. В случае, если после выполнения генетических операторов скрещивания и мутации будет получена особь, не удовлетворяющая этим условиям по одной или нескольким хромосомам, то данная особь будет оштрафована в виде обнуления значения функции приспособленности, что позволит исключить решение, не удовлетворяющее исходных ограничениям из дальнейшего рассмотрения.
2.4 Селекция хромосом
2.4.1 Задача метода селекции хромосом
Задача метода селекции заключается в выборе особей для следующего поколения, т.е. де факто, от того, насколько эффективным будет этот выбор зависит скорость сходимости ГА. В классическом ГА могут применяться несколько видов селекции хромосом: · метод рулетки - самый простой и распространенный метод селекции, заключающийся в отборе родительских особей пропорционально значениям их функций приспособленности;
· турнирная селекция предполагает разбиение популяции на группы и выбор в каждой из них наилучшей особи, что считается более эффективным, чем метод рулетки [6];
· ранговая селекция заключается в ранжировании особей по убыванию их значений функций принадлежности;
· пороговая селекция - частный случай ранговой селекции, в котором функция, определяющая вероятность перехода особи в родительский пул, имеет форму порога;
· уплотненная селекция заключается в замещении родительских особей наиболее похожими на них потомками, что позволяет сохранить разнородность популяции на протяжении всей работы ГА.
Для обеспечения большей гибкости решения задачи предоставим пользователю самому возможность выбора метода селекции.
2.4.2 Алгоритм селекции методом рулетки
Метод рулетки заключается в использовании принципа колеса рулетки и позволяет выбирать родительские особи пропорционально значениям их функций приспособленности. Информации об особях представляется в виде секторов рулетки, при этом, чем больше значение функции приспособленности особи, тем больше сектор колеса рулетки.
, (23) где e - представляет относительную величину сектора рулетки;
F(chi) - значение функции приспособленности для i-ой хромосомы;
- среднее значение функции приспособленности.
Входными данными алгоритма (23) является вектор значений функций приспособленности особей текущей эпохи - Fitness. Функция Count возвращает количество элементов переданного вектора.
Колесо рулетки может быть представлено в виде числового интервала (например, от 0 до 1), в котором каждая особь ассоциируется с подинтервалом, длина которого пропорциональна величине значения функции приспособленности для этой особи. Вектор Lambda содержит вещественные значения в интервале [0,1], которые определяют размер соответственного подинтервала и, как следствие, вероятность выбора той или иной особи для включения в родительский пул следующей эпохи. Метод селекции будет заключаться в выбросе случайного значения из интервала [0,1] и определении в подинтервала, в который попадает случайное значение.
Данные о длинах интервалов для выполнения селекции методом рулетки могут быть получены в соответствии со следующим алгоритмом (рис. 5)
Рисунок 5 - Получение данных для метода рулетки
К недостаткам этого метода относят: · можно применять только для положительных значений функции приспособленности;
· присутствует преждевременная сходимость алгоритма за счет быстрого исключения особей с малыми значениями функций приспособленности.
2.4.3 Алгоритм турнирной селекции
В основе селекции методом турнирной селекции лежит метод разделения особей популяции на подгруппы.
Подгруппы могут иметь произвольный размер, но чаще всего размер подгруппы выбирают равным двум или трем особям. Схематично турнирный метод представлен на рисунке 6.
Рисунок 6 - Схема турнирной селекции
Исследования подтверждают, что применение турнирного метода селекции более эффективно, чем метода рулетки [6].
2.4.4 Алгоритм пороговой селекции
Пороговая селекция является частным случаем метода ранговой селекции, в котором функция, определяющая вероятность перехода особи в родительский пул имеет форму порога (рис. 7).
Рисунок 7 - График пороговой функции метода пороговой селекции
Как видно на рис.7 после некоторого порогового значения функции приспособленности особи перестают включаться в родительский пул. Такая форма позволяет устанавливать определенный уровень селективного давления за счет управления высотой порога, от которой зависит уровень приспособленности особи. Количество копий каждой особи, введенных в родительскую популяцию, рассчитывается в соответствии с пороговой функцией: чем больше приспособленность особи, тем больше его копий будут включены в родительский пул на следующей эпохе. Ранжирование особей выполняется с использованием известных методов сортировки массивов.
2.4.5 Алгоритм уплотненной селекции
Уплотненная селекция представляет собой метод выбора особей, в результате которого от эпохи к эпохе похожие особи замещаются похожими. Мерой похожести особи является расстояние Хемминга, вычисляемое как количество генов хромосом имеющих различное значение для двух особей. В алгоритме для этих целей определена функция DISTANCEHAMMING().
В алгоритме предопределяется целочисленный параметр CF (crowding factor), который определяет количество родителей, похожих на заданную особь. Если таких родителей больше, то лишние особи исключаются из родительской популяции. Также в качестве параметра задается целое число HAMLIM, определяющее максимальное значение меры Хемминга, при которой особи считаются похожими.
Целью выбранного подхода является сохранение как можно большей разнородности популяции. Таким образом, метод уплотненной селекции позволяет исследовать большую область поиска, решая при этом проблему преждевременной сходимости ГА. Блок-схема алгоритма метода уплотненной селекции представлена на рисунке 8.
Рисунок 8 - Блок-схема метода уплотненной селекции
В качестве входных данных метода выступают вектор особей, полученный на предыдущей эпохе - CH1 и вектор особей, полученных из СН1 с применением генетических операторов скрещивания, мутации и инверсии - CH2. При этом Count(CH2) > Count(CH1).
2.5 Увеличение сходимости генетического алгоритма
Рассмотрим два метода, позволяющих увеличить сходимость рассматриваемого ГА. Первый из них - элитарная стратегия - подразумевает гарантированное попадание в родительский пул следующей популяции особи с наилучшим значением функции приспособленности, тем самым защищая наилучшие решения. Эта стратегия позволяет увеличить скорость сходимости ГА [6,8].
Второй метод - масштабирование функции приспособленности - применяется для предотвращения преждевременной сходимости, т.е. случая, когда в популяции начинают доминировать наилучшие, но не оптимальные хромосомы (локальный экстремум). Линейное масштабирование заключается в применении следующей зависимости (24):
, (24) где a, b - константы подбираемые таким образом, чтобы среднее значение функции приспособленности до и после масштабирования были равны, а максимальное значение было кратным ее среднему значению;
F, F’ - значение функции приспособленности соответственно до и после масштабирования.
Мы будем применять масштабирования функции приспособленности, согласно (24) в том случае, если темп возрастания значений функции приспособленности будет падать.
Для идентификации последнего факта будем использовать информацию о n предыдущих эпохах. Будем считать, что значения функции приспособленности перестали существенно меняться (т.е. решение найдено и ГА необходимо остановить) в случае, если выполняется неравенство: , (25) где t - номер текущей (последней) эпохи;
n - число эпох, влияющих на принятие решения;
Vi - функции приспособленности лучшей особи в эпохе i;
? - константа, определяющая факт существенного снижения скорости возрастания значения функции принадлежности наилучшей особи.
Нетрудно понять, что это выражение (25) представляет собой среднее значение квадратов отклонений предыдущих максимальных значений функций приспособленности в n последних эпохах от крайнего значения. При этом, введен коэффициент забывания, обратно пропорциональный длине расстояния от текущей эпохи до той в которой вычисляется квадрат отклонения.
2.6 Разработка алгоритма работы программы
Общий алгоритм работы программы по решению поставленной задачи расчета химического равновесия можно разделить на несколько последовательных этапов (рис.9).
Во-первых, необходимо произвести инициализацию компонентов, участвующих в расчете, добавив информацию о них в БД, либо воспользовавшись уже имеющимися данными.
Во-вторых, необходимо установить начальные значения и параметры проводимого расчета, такие как температура, давление, количество компонент и их начальные массы.
Затем данные, полученные на первых двух этапах передаются самостоятельному модулю расчета, реализующему рассмотренный выше ГА. Очевидно, что этот этап является наиболее важным и ресурсоемким.
Рисунок 9 - Общий алгоритм работы программы
После завершения работы модуля расчета требуется собрать полученные данные и представить их пользователю в удобном виде (таблицы, графики и т.д.). Общий алгоритм работы программного средства, таким образом, представляет собой последовательность выполнения заявленных этапов.
Рассмотрим более подробно алгоритмы, относящиеся к разработке клиентской части приложения и реализующие блоки алгоритма «Инициализация параметров расчета» и «Представление результатов»
2.7 Взаимодействия с пользователем
2.7.1 Авторизация пользователей на ресурсе
Разрабатываемое программное средство проектируется как многопользовательское и функционирующее в сети. Отвлекаясь от методов реализации подобных систем (они будут рассмотрены в следующем разделе) необходимо отметить, что для большинства подобных систем характерно наличие возможностей по разделению доступа к функциям программного средства для различных категорий пользователей.
Так и в данном случае, требуется разделить пользовательское влияние как минимум на две роли: незарегистрированный и зарегистрированный пользователь. В первом случае, пользователю веб-ресурса доступны только функции по выполнению расчета равновесия для уже имеющихся в БД химических компонентов, при этом пользователю недоступно изменение их параметров. Во втором случае, пользовате
Вывод
В ходе выполнения дипломной работы было спроектировано и реализовано программное средство вычисление химического равновесия с применением генетического алгоритма. Данное программное средство реализовано по клиент-серверной архитектуре, представляет собой совокупность веб-приложения и исполняемого модуля, является кроссплатформенным и свобдно-распространяемым.
Предметом рассмотренных в работе приложений термодинамического анализа являются многокомпонентные химически активные газы, актуальные для естественных наук и техники. Применение результатов данной работы к равновесным (а при некоторой модификации и к стационарным) физико-химическим системам практически не ограничено: от горения топлив в энергетических и транспортных установках, превращения вредных антропогенных выбросов в атмосфере - до технологи сложного органического синтеза.
Список литературы
1. Чепмен С., Каулинг Т. Математическая теория неоднородных газов. М.: Иностр. лит., 1960.
2. Бенсон С. Термохимическая кинетика. М.: Мир, 1971.
3. Степанов Н.Ф., Ерлыкина М.Е., Филиппов Г.Г. Методы линейной алгебры в физической химии. М.: Изд-во МГУ, 1976.
4. Физико-химические процессы в газовой динамике: Компьютеризованный справочник. В 3-х томах / Под ред. Г.Г. Черного и С.А. Лосева. М.: Изд-во МГУ, 1995-2002.
5. Ермаков С.М., Михайлов Г.А. Курс статистического моделирования. М.: Наука, 1976.
6. Лешек Рутковский. Методы и технологии искусственного интеллекта. М.: Горячая линия - Телеком, 2010 г.
9. Генетические алгоритмы [Электронный ресурс] - URL: 10. Информатика. Лекция №5. Представление чисел в компьютере. [Электронный ресурс] - URL: 11. Квентин Зервас. Web 2.0: создание приложений на PHP. М.: ООО «И.Д. Вильямс», 2010
12. СНИП II-90-81 «Производственные здания промышленных предприятий», [Электронный ресур] - URL:
Приложение А Техническое задание на программное средство
«СОГЛАСОВАНО» Руководитель дип. проекта: ____________ Жуков А.И. «____» ____________ 2012 г. «УТВЕРЖДЕНО» зав. кафедрой «ПОВТ и АС» _____________ Нейдорф Р.А. «____» ____________ 2012 г.
П.А.1 Введение
П.А 1.1 Наименование программы
Наименование программы - «Web-сервис расчета параметров химического равновесия».
П.А 1.2 Область применения
Областью применения данного программного продукта являются сфера научных исследований и высшего профессионального образования.
П.А 1.3 Объект внедрения
Конечный программный продукт предназначен для внедрения в образовательный процесс кафедры «Программное обеспечение вычислительной техники и автоматизированных систем» ДГТУ.
П.А.2 Основания для разработки
Разработка ведется на основании документа «Учебный план для студентов ВУЗА», факультета «Информатика и вычислительная техника», обучающихся по специальности 230105 - «Программное обеспечение вычислительной техники и автоматизированных систем», в соответствии с которым студенты, заканчивающие ВУЗ, должны предоставить к защите выпускную квалификационную работу, подтверждающую присвоение им квалификации «инженер программист». Предметным основанием является задание на дипломную работу.
П.А.3 Назначение разработки
П.А.3.1 Функциональное назначение
Функциональное назначение программного средства заключается в предоставлении web-интерфейса решения задачи расчета параметров химического равновесия с использованием биоинспирированного подхода.
П.А.3.2 Эксплуатационное назначение
Эксплуатационное назначение заключается в использовании программного средства в качестве образовательного web-ресурса кафедры «Программное обеспечение вычислительной техники и автоматизированных систем» ДГТУ в локальной и глобальной сетях.
П.А.4 Требования к программе
П.А.4.1 Требования к функциональным характеристикам
Общими для сайта в целом являются следующие требования: · сайт должен содержать полную и актуальную информацию о химических элементах;
· пользовательский интерфейс по доступу к информации должен быть интуитивно понятным широкому кругу пользователей;
· главная страница должна быть выполнена таким образом, чтобы: § посетителю: ° помочь выбрать нужный состав компонент для проведения расчета;
° обеспечить возможность поиска информации о компонентах и элементах по их названиям;
° обеспечить возможность просмотра и выгрузки результатов расчета;
§ администратору ресурса: ° предоставить инструмент редактирования и добавления информации о химических элементах и доступных компонентах;
° обеспечить возможность просмотра показателей проведенных расчетов;
· удобная навигация между страницами ресурса с использованием технологии breadcrumbs;
· отображение запрошенной информации должно осуществляться за минимальное количество перегрузок страниц и с минимальным количеством запросов к серверу.
П.А.4.1.1 Требования к структуре и функционированию
Структурно ПС должно состоять из следующих компонент (подсистем): · подсистема хранения данных;
· интерфейс взаимодействия с ресурсом.
Подсистема хранения данных должна обеспечивать хранение в БД необходимых для сайта данных и выборку из БД объектов для формирования информационного контента сайта. В БД должна храниться информация о химических элементах и доступных компонентах, а также сопутствующая информация используемая для параметризации расчета и представления результатов конечному пользователю.
Интерфейс взаимодействия с ресурсом должен обеспечивать возможность добавления новых данных о химических элементах, компонентах (химических соединениях), а также внесение дополнительной информации, предназначенной для управления генетическим алгоритмом. Для этого должен быть реализован механизм. Авторизация пользователей должна основываться на уникальных идентификаторе и пароле пользователя и выполняться существующими на информационно-образовательном портале методами.
В системе должны быть предусмотрены три основных типа пользователей: · неавторизованный пользователь: ограниченные возможности использования расчета (по числу и составу компонентов);
· авторизированный пользователь: неограниченные возможности использования расчета по уже имеющимся компонентам и химическим элементам;
· администратор: авторизованный пользователь, обладающий полномочиями для добавления новых и редактирования существующих данных о химических элементах и соединениях.
П.А.4.1.2 Требования к дизайну
Должен согласоваться с дизайном применяемым на портале и должен удовлетворять следующим требованиям: · быть достаточно «легким» по объему графических элементов и обеспечивать как можно большую скорость загрузки страниц сайта;
· обеспечивать легкую идентификацию раздела сайта, в котором находится пользователь;
· обеспечивать минимум усилий и временных затрат пользователя для навигации по страницам сайта;
· содержать исчерпывающий набор метаданных для эффективного индексирования поисковыми системами и корректного автоматического выбора кодировки.
П.А.4.1.3 Организация входных данных
В качестве входные данные выступают: · таблицы БД справочников химических элементов;
· массы химических элементов;
· параметры генетического алгоритма (предельное количество итераций, температура и давление компонентов расчета);
П.А.4.1.4 Организация выходных данных
В качестве выходной информации выступает таблица масс реагентов при минимальном термодинамическом потенциале системы для равновесного состояния.
П.А.4.2 Требования к надежности
Надежность во многом обеспечивается хостинг-провайдером. Мощные высокопроизводительные серверы обеспечивают стабильную работу сайта. Регулярно осуществляется резервное копирование данных.
Многопользовательский режим с различными правами на доступ к информации.
П.А.4.3 Требования к условиям эксплуатации
П.А.4.3.1 Условия эксплуатации технических средств
Для функционирования программного средства необходимо выполнение основных правил и требований к безопасной эксплуатации ЭВМ и всех составляющих ее компонентов. Такими требованиями могут выступать: диапазон температур, запыленность и загазованность помещения и т.д.
Дополнительных требований и ограничений к условиям эксплуатации не предъявляется.
Требования к пользователю: пользователь должен владеть базовыми навыками работы с компьютером и иметь навыки работы с Интернет браузером Opera, Mozilla, или любым другим Интернет браузером, поддерживающим язык гипертекстовой разметки HTML.
П.А.4.3.2 Требования к видам обслуживания
Программное средство не требует проведение каких-либо дополнительных видов обслуживания. Используемые в разрабатываемой системе технические и программные средства должны обеспечивать непрерывную и круглосуточную работу без постоянного присутствия персонала технического обслуживания.
П.А.4.3.3 Разделение доступа
Так как разрабатываемая подсистема является частью системы информационно-образовательного портала, то самостоятельное реализация модулей разделения доступа и аутентификации не предполагается.
П.А.4.3.4 Администрирование пользователей
Так как разрабатываемая подсистема является частью системы информационно-образовательного портала, то самостоятельное администрирование пользователей реализовывать не предполагается.
П.А.4.3.5 Главная страница ресурса
Главная страница ресурса состоит из: контентной области, которая предлагает посетителю выбрать интересующий его вариант расчета.
П.А.4.3.6 Графическая оболочка внутренних страниц
Графическая оболочка внутренних страниц это: · контентная шапка сайта, общая для всех сервисов информационно-образовательного портала;
· горизонтальная навигация в виде меню;
· контентное содержание страницы выбора параметров расчета, либо графическое или табличное содержание страницы представления результатов расчета;
· внизу страницы отображается графическая часть, содержащая адрес и контактные данные учебного заведения.
П.А.4.3.7 Описание контента разделов сайта
Зайдя на сайт посетителю предлагается: · главная страница ресурса, которая поможет выбрать, интересующие его параметры расчета;
· страница с теоретической информацией о проводимых расчетах и о реализуемом методе с использованием генетического алгоритма;
· страница просмотра информации о результатах расчета.
П.А.4.4 Требования к составу и параметрам технических средств
Предъявляются следующие требования к минимальному составу технических средств ПК.
Для сервера: · Web-сервер Apache 2.x и выше;
· СУБД Postgres 9.0 и выше;
· интерпретатор PHP 5.3 и выше;
· операционная система семейства Linux - Debian.
Для клиента: · браузер Opera 10.x, Mozilla FF 6, IE 8, Google Chrome 12 и выше;
· операционная система Windows XP и выше или Linux, Unix с графическим интерфейсом (KDE, GNOME);
· доступ в Интернет или к ЛВС ДГТУ;
· 32 или 64 разрядный процессор семейства Intel Pentium (или любой другой процессор, совместимый с ним по набору инструкций) с тактовой частотой 336 Ghz или выше;
· оперативная память не менее 1024 МБ;
· стандартные устройства ввода - вывода.
П.А.4.5 Требования к информационной и программной совместимости
Программное средство является кроссплатформенным, функционирует под управлением операционной системой семейства Windows или Linux. Для использования созданного сайта, его необходимо загрузить в любом современном браузере
Сайт выполнен с помощью языка гипертекстовой разметки HTML, с использованием языков JAVASCRIPT, PHP и применением технологии JQUERY/AJAX. Содержит все необходимые модули, не требует использования внешних библиотек.
П.А. 4.6 Требования к маркировке и упаковке
Требования к маркировке и упаковке отсутствуют.
П.А.4.7 Требования к транспортированию и хранению
Условия транспортирования, места хранения, условия складирования и сроки хранения в различных условиях должны соответствовать требованиям, предъявляемым к носителям информации на которых будет содержаться данное программное изделие. Сайт может храниться на жестком диске, на Flash-носителе, на компакт-дисках.
П.А.5 Требования к программной документации
Предварительный состав необходимой программной документации, выполненной на русском языке в соответствии с требованиями ЕСПД согласно ГОСТ 19.201-78, 19.503-79, 19.504-79, 19.505-79: Техническое задание по ГОСТ 19.201-78 ЕСПД. «Техническое задание. Требования к содержанию и оформлению».
П.А.6 Стадии и этапы разработки
Системный анализ (с 10.01.2012 по 25.01.2012): · определение функционала;
· определение области применения и целей использования разрабатываемого программного средства;
· поиск вариантов решения поставленных задач;
· подготовка технического задания;
· выбор и подготовка инструментальных средств и средств отладки.
Общесистемное проектирование (с 25.01.2012 по 04.03.2012): · определение структуры программного комплекса;
· определение структуры алгоритмов и модулей.
Программная реализация, рабочий проект (с 4.03.2012 по 24.04.2012): · разработка алгоритмической части;
· разработка текстов программных модулей;
· проектирование пользовательского интерфейса.
Отладка программного средства в статике (с 24.04.2012 по 15.05.2012): · тестирование программных модулей;
Тестовые испытания программного комплекса (с 30.05.2012 по 10.06.2012): · испытание на информационную полноту;
· испытание на полноту функционирования;
· протоколы и акты испытаний.
П.А.7 Порядок контроля и приемки
Порядок и контроль приемки определяются заведующим кафедрой «ПОВТ и АС» и основаны на демонстрации знаний технологии и умении создавать программные средства для различных предметных областей. Главным требованием к приемке является наличие правильно работающей программы иллюстрируемой тестовым примером и отчета, представленного в печатном виде.