Разработка программного средства расчета химического равновесия

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ДОНСКОЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

ДГТУ

Кафедра «Программное обеспечение вычислительной техники и автоматизированных систем»

«ПОВТ и АС»

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к преддипломной практике на тему

Разработка программного средства расчета химического равновесия

Практикант Олипир Михаил Викторович Группа ВИS-31

Специальность 230105 - Программное обеспечение вычислительной техники и автоматизированных систем

Руководитель работы /Жуков А.И./

Нормоконтролер ______________ Котельникова И. В./

Ростов-на-Дону 2012 г.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ДОНСКОЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

ДГТУ

Кафедра «Программное обеспечение вычислительной техники и автоматизированных систем»

«ПОВТ и АС»

Задание

на преддипломную практику

Студент Олипир Михаил Викторович Группа ВИS-31

Тема Разработка программного средства расчета химического равновесия

Срок представления отчета к защите " 03 " марта 2012 г.

Исходные данные для преддипломной практики Разработать программное средство для выполнения расчета химического равновесия с использованием генетического алгоритма

Руководитель работы / Жуков А. И. /

Задание принял к исполнению _______________ Олипир М.В./

« ____» ___________2012 год

Реферат

Отчет содержит: листов - 60, рисунков - 11, таблица 1, приложений - 1.

Ключевые слова: ГЕНЕТИЧЕСКИЙ АЛГОРИТМ, ХИМИЧЕСКОЕ РАВНОВЕСИЕ, ВЕБ-ПРИЛОЖЕНИЕ.

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

Введение

Протекание реальных процессов в физико-химических системах зависит от большого числа компонентов, их температуры и давления. Они включают в себя многостадийные химические превращения, фазовые переходы, явления переноса массы и энергии. При этом справедливо утверждение о том, что химическая реакция способна нарушить термодинамическое равновесие [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.

Рисунок 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 Авторизация пользователей на ресурсе

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

Так и в данном случае, требуется разделить пользовательское влияние как минимум на две роли: незарегистрированный и зарегистрированный пользователь. В первом случае, пользователю веб-ресурса доступны только функции по выполнению расчета равновесия для уже имеющихся в БД химических компонентов, при этом пользователю недоступно изменение их параметров. Во втором случае, пользователь получает расширенный доступ к интерфейсу: он может создавать справочники, редактировать их структуру и данные, добавлять информацию о химических компонентах и т.д.

Рассмотрим алгоритм авторизации пользователя на ресурсе (рис. 10).

Рисунок 10 - Алгоритм авторизации пользователя

Меню пользователя является главным источником информации о том, какие функции системы ему доступны.

2.7.2 Модификация контента системных справочников

Как уже было отмечено выше, авторизованному пользователю доступно изменение структуры и содержимого справочников о химических элементах. Рассмотрим более подробно алгоритм выполнения обновления/удаления данных из справочников БД (рис.11).

Рисунок 11 - Алгоритм выполнение модификации данных в системных справочниках

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

В следующем разделе рассмотрена программная реализация представленных алгоритмов.

3. Программная реализация Генетического Алгоритма для расчета химического равновесия

3.1 Архитектура программного средства

Разрабатываемое программное средство в соответствии с предложенным общим алгоритмом работы его работы (рис. 9) должно включать в себя несколько компонентов. Также при проектировании архитектуры программного средства необходимо учесть требование в доступе по сети к функциям расчета химического равновесия. В этой связи наиболее подходящей схемой реализации приложения нам представляется гетерогенный подход к разработке модулей ПС.

Наиболее быстрым с точки зрения разработки сетевых приложений сегодня является вариант разработки веб-приложения. Этот подход имеет большое количество плюсов по сравнению с разработкой классического клиент-серверного приложения, к основным из которых можно отнести: скорость разработки, универсальность протокола обмена, минимальное количество необходимого предустановленного программного обеспечения на клиентской стороне (программа интернет-обозреватель).

Классическое веб-приложение сегодня может быть представлено как совокупность серверных сценариев на одном из популярных языков разработки (например, PHP), функциональность которых обеспечивается веб-сервером (например, Apache) [11]. Пользователь адресует свой запрос веб-серверу, который по параметрам запроса (таким как url, массив post и т.д.) определяет какой скрипт должен быть выполнен. Результат работы скрипта возвращается пользователю. Для выполнения функций по модификации и представлению контента на клиентской стороне, как правило, используются возможности языка Java Script.

Таким образом, модули занесения данных о компонентах, установки параметров расчета и представления результатов будут реализованы по типу веб-приложения.

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

Язык C++ зарекомендовал себя не только, как универсальное средство для написания программ любой сложности (от драйверов до крупных распределенных систем), но и как относительно быстрое средство выполнения обработки данных. Поэтому в рассматриваемой концепции, модуль выполнения расчетов будет реализован как автономное приложение, запуск которого инициируется серверными скриптами.

Таким образом, нами реализуется следующая архитектура программного средства (рис.12).

Рисунок 12 - Архитектура программного средства

Работа с БД компонентов, а также установка параметров расчета производятся конечным пользователем программного средства с использованием веб-интерфейса из любого современного браузера. Установленные параметры передаются серверной стороне. Происходит серия запросов к БД для уточнения параметров выбранных пользователем компонентов, после чего формируется конфигурационный файл, передаваемый модулю расчета, и происходит запуск программного средства на стороне сервера. После этого управление передается клиентской стороне, которая с заданным тайм-аутом запрашивает на сервере информацию о проводимом расчете. Как только результаты расчета могут быть представлены, происходит их табличная и графическая интерпретация на клиентской стороне (в веб-браузере).

3.2 Обоснование выбора средств разработки

Как уже было отмечено выше в качестве средств разработки модулей для работы с базой данных, а также для представления интерфейса пользователя был выбран язык PHP 5.3. PHP - широко используемый язык скриптинга (сценариев) общего назначения, который особенно подходит для web-систем и может быть внедрен в HTML. Одна из наиболее сильных и привлекательных черт PHP - поддержка им большого количества СУБД.

В качестве СУБД нами выбрана PostgreSQL 9.0. PostgreSQL -- свободная объектно-реляционная система управления базами данных (СУБД). Она является свободной альтернативой коммерческим СУБД (таким как Oracle Database, Microsoft SQL Server). Сильными сторонами PostgreSQL считаются:

· поддержка БД практически неограниченного размера;

· мощные и надежные механизмы транзакций и репликации;

· наследование;

· легко расширяемая система типов.

Последней тенденцией в разработке веб-приложений является разработка, так называемых, активных веб-страниц, которые могут модифицировать свой контент уже после загрузки. В качестве преобладающего средства для реализации этих функций, выступает скриптовый кросс-браузерный язык Java Script с использованием технологии AJAX и методов обмена с серверной стороной по технологии JSON.

Разработка модуля выполнения расчетов выполняется на языке C++, основными преимуществами которого являются высокая функциональность, скорость работы приложений и использование объектно-ориентированной парадигмы. В качестве входных данных для данного программного модуля выступают генерируемые скриптами конфигурационные файлы, содержащие параметры расчета и информацию о компонентах, участвующих в нем. В качестве выходной информации, модулем генерируются текстовые файлы с полученными значениями масс для каждого из компонентов, а также с другими характерными параметрами выполнения ГА (такими как количество эпох, скорость работы алгоритма, метод селекции и т.д.).

3.3 Схема отношений БД

Для хранения данных о компонентах системы используется следующая схема отношений БД (табл. 1).

Таблица 1 - Схема отношений реляционной БД

Element	Отношение «Химический элемент»
Id	Целое	Идентификатор (PK)
letter	Строка(5)	Обозначение химического элемента, например H
name	Строка(20)	Название химического элемента, например «водород»
am	Целое	Атомная масса элемента
Component	Отношение «Компонент расчета»
Id	Целое	Идентификатор (PK)
name	Строка(40)	Название компонента, например «вода»
enthalpy	Целое	Энтальпия компонента
entropy	Вещественное	Энтропия компонента
heat_capacity	Вещественное	Теплоемкость
Composition	Отношение «Состав»
element_fk	Целое	Внешний ключ на кортеж отношения Element
component_fk	Целое	Внешний ключ на кортеж отношения Component

Объекты предметной области и характер связей между ними представлены на ER-диаграмме (рис. 11).

Рисунок 13 - ER-диаграмма БД

Очевидно, что для организации связи «многие-ко-многим», имеющей место между сущностями «Химический элемент» и «Компонент расчета», необходимо создать дополнительное отношение. Мы реализовали отношение «Composition», состоящее из пар внешних ключей на объекты отношений «Element» и «Component», что отражено на ER-диаграмме (рис.13). Скрипт создания реляционной базы данных в соответствии с описанной схемой отношений представлен в приложении Б.

3.4 Реализация веб-приложения

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

В качестве программно-алгоритмического каркаса разработки приложения был выбран популярный фреймворк CodeIgniter, реализующий структуру Model-View-Controller. Model-View-Controller (Модель-Представление-Контроллер) - это популярный сегодня шаблон проектирования, основной идеей которого является отделение обработки данных от формы их отображения. Составные части данного шаблона представлены на рисунке 14.

Рисунок 14 - Концепция MVC

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

Рассмотрим структуру реализованного веб-приложения с точки зрения архитектуры выбранного программно-алгоритмического каркаса:

· контроллеры:

§ Auth - базовый контроллер авторизации, реализующий методы по выполнению аутентификации пользователей, управлению данными о пользователях в сессиях веб-сервера, формированию меню и отображению общих для всех страниц элементов веб-приложения (шапка сайта, общие js-скрипты и css-стили);

§ Dicts - контроллер, определяющий процедуру взаимодействия авторизованных пользователей с системными справочниками (их создание, модификация и наполнение данными);

§ Calc - контроллер выполнения расчета, реализующий методы по представлению данных пользователю о параметрах расчета, а также предоставляющий доступ к методам модели расчета;

· модели:

§ Auth_model - модель отвечающая за авторизацию пользователей и представляющая методы по проверке валидности данных авторизации, а также получению информации о том, произведен ли вход на сайт и о том, кем он был произведен;

§ Dict_model - модель для взаимодействия с системными справочниками (получение метаинформации о существующим справочниках, получение данных справочников, выполнение скриптов создания и удаления справочников);

§ Calc_model - модель, определяющая логику взаимодействия веб-приложения с внешними программными модулями (рис. 12), реализующими алгоритм расчета;

· представления:

§ dict/add - добавление справочника;

§ dict/composition - определение состава химических компонентов;

§ dict/data - модификация контента справочников;

§ dict/list - просмотр списка существующих справочников;

§ calculate - представление данных для расчета;

§ foot - нижняя часть страницы (общая для всех страниц сервиса);

§ head - верхняя часть страницы (включая скрипты и стили);

§ login - форма авторизации;

§ menu - представление главного меню;

§ result - представление результатов рачета.

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

// Контроллер auth.php

// Выполнение авторизации

public function login()

{

// загрузить модель авторизации

$this->load->model('auth_model','auth');

// Обрабатываются только AJAX запросы

if ($this->input->is_ajax_request() === false)

{

return $this->index(); // иначе выкинуть на главную страницу

}

// Проверить логин (данные передаются в POST)

$login = $this->input->post('login');

$password = $this->input->post('pass');

// если не залогинен, то вывести форму авторизации

if ( ! $this->auth->isSmbLogin() )

{

if ($this->auth->login($login, $password))

{

$this->messages[] = 'Вы успешно зарегистрированы в системе';

}

else // ошибка

{

$this->errors[] = 'Неверный логин и/или пароль, либо пользователь уже неактивен. Для восстановления пароля обратитесь к администратору.';

}

} else {

$this->errors[] = 'Уже авторизован!';

}

// возврат данных в виде JSON

if ( count($this->errors) > 0 ||

count($this->messages) > 0 ||

count($this->callback_data) > 0 ) {

print json_encode(array('errors' => $this->errors,

'messages' => $this->messages,

'data' => $this->callback_data));

}

}

Для того, чтобы использовать код проверки прав и управления данными в сессии было возможно во всех контроллерах приложения при их создании в качестве родителя (в терминологии объектно-ориентированной парадигмы) или базового контроллера выбирается как раз контроллер Auth, после чего все методы, реализуемые данным контроллером, становятся доступны его наследникам. Кроме того, такая структура приложения позволяет реализовать методы проверки аутентификации и управления сессиями подключения пользователей в одном месте, что безусловно благотворно сказывается на качестве разрабатываемого проекта и его безопасности с точки зрения несанкционированного доступа к информационному контенту веб-приложения.