ЭФФЕКТИВНЫЙ ГЕНЕТИЧЕСКИЙ АЛГОРИТМ ДЛЯ СТРАТЕГИИ ВЫБОРА ЭЛЕМЕНТА

Авторы: Koun-Tem Sun*, Yi-Chun Lin, Yueh-Min Huang

Dep. of Information and Learning Technology*, National University of Tainan*

Dep. of Engineering Science, National Cheng Kung University

Источник: http://elearning.lib.fcu.edu.tw/bitstream/2377/3728/1/ce07ics002006000254.pdf

Перевод: Трофменко Е.С.

Аннотация

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

1: Введение

Item Response Theory (IRT) теория тестов, основанная на степени сложности тестового задания, степени отличия, степени спекуляции и способности теста в определении параметров, нужных для проведения анализа. В одномерных случаях, наблюдаются следующие преимущества: сложность теста оценивается независимо с помощью его элементов, степень трудности и степени дискриминации не относится к испытуемым выборки. Точность определения оценки так же оценивается [10]. Так же в терминах создания тестов, различные возможны вариации тестовых заданий [1, 2, 7, 11, 20, 28]. Таким образом, при построении теста IRT не только превосходит классическую теорию, но и заменяет ее. В процессе создания тестов с помощью IRT, используют стратегию выбора элементов, основанную на целях разработчиков. В настоящее время как TOEFL Test, так и локальный базовый академический тест содержит банк тестовых вопросов, из которого формируется тестовая последовательность. Поэтому все больше и больше ученые в настоящее время уделяют исследованиям, связанных со стратегией выбора элементов [18, 12, 16, 17, 19].

Стратегия выбора элемента – это задача комбинаторной оптимизации. Когда увеличивается банк вопросов, время для расчетов увеличивается в несколько раз [14]. Пока ученые доказали, что это является NP-трудной задачей [24] и этот вопрос предполагает многошаговый расчет в формировании лучшего решения. Генетические алгоритмы могут быть решением в данной ситуации. Этот метод был широко применен в научных и инженерных задач ах [13, 23, 3, 4, 5, 9, 21, 8]. Более того, некоторые ученые также применили простой генетический алгоритм на ряде тестовых элементах и информационных функциях, также как и стратегия выбора элементов, которые не имеют дополнительных ограничений, но показывают выдающиеся результаты. [18, [19]. Тем не менее, поскольку тесты требуют гибкости, а выбор элементов часто вовлекает ограничения для поставленных целей [5, 15, 25, 26, 27], этот вопрос называется оптимизационной задачей с ограничениями[5]. Когда решается проблема оптимизации с ограничениями, в генетических алгоритмах часто используется штраф-функция. Она простая и легко реализуемая; вместе с тем, серьезную озабоченность состоит в том, "может ли быть найден соответствующий штрафной параметр? "[5, 6]. Таким образом, ученый K. Деб предложил другой вид эволюционного метода для решения этой проблемы. Особенность: нет необходимости в штрафном параметре. Оператор турнирного выбора используется для создания пар и сравнения. В то время как евклидово расстояние и мутационные расчеты используются для поддержания целесообразности и гибкости решений. В то же время, достигается лучшая эффективность [5].

В связи с вышеизложенным, простой генетический алгоритм показывает хорошие результаты при использовании в стратегии выбора элементов. Тем не менее, не было глубокого и четкого обсуждение ограничительных условий. Таким образом данная статья показывает эволюционную методику в стратегии выбора элементов с ограничительными условиями, и обеспечивает возможность выбора элементов. В разделе 2, будет представлен простой генетический алгоритм. В разделе 3, будет представлен генетический алгоритм Деба для стратегии выбора элементов. В разделе 4 – иерархический генетический алгоритм для стратегии выбора элемента, в разделе 5 – оценка эффективности. И, наконец, выводы и рекомендации.

2: Простой генетический алгоритм стратегии выбора элемента.

В применении ГА для проблемы выбора элементов, каждая хромосома представляет собой множество тестов k, которое содержит n бит (соответственно числу тестов в банке = n), среди которого m бит(количество тестовых вопросов = m) равно 1, а остальные равны 0. xi указывает на то, присутствует ли вопрос в тестовой последовательности (xi = 1, да; xi = 0, нет). Для каждой хромосомы, можно вычислить информационную емкость результируемого теста и отклонение от только что созданных тестов. Квадрат суммы отклонений определяется как часть фитнес-функции в эволюционного процесса. , где dj – ссылается на значение целевой информации о способности уровеня j, j(=1~s) – способность уровня, s – количество уровней. , где ссылается на k-ю хромосому и емкость теста на j-м уровне. i(=1~n) i-й элемент в банке вопросов, n – количество вопросов в банке. wij – емкость i-говопроса на j-м уровне. выбор i-го условия в k-й хромосоме.

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

(Анимация: объем – 14 КБ; размер – 587х664; количество кадров – 8; задержка между кадрами – 50 мс; задержка между первым и последнимкадрами – 4000 мс; количество циклов повторения – бесконечное.)

1. Установка начальной популяции и параметров эволюционного процесса: случайно генерируется n бинарных строк, состоящих из P хромосом. Каждая хромосома – 1, а остальные 0. Вероятности кроссинговера, мутации и репродукции устанавливаются в переменные Pc, Pm, и Pr соответственно. Эволюционна алгебра – T, начальное значение равно 0, и максимальное значение установлено в gener _ no.

2. Расчет значений фитнесс-функции для всех хромосом в популяции и определение оптимизированной фитнесс хромосомы chromosomeopt: , где число, удовлетворяющее условию , где ссылка на целевую функцию, q(=1~p) – число q констант; p – общее число констант Сq – количество q констант, включая множественные вопросы. kq, kq – параметры для значения q-го ограничителя, rk – число ограничений.

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

3.1. Применяется 2х точечный кроссинговер для каждой пары родителей с вероятностью Pc.

3.2 используется 2х точечная мутация с вероятностью Pm. Случайно выбирается хромосома из родительской популяции и в ней выбирается 2 позиции. Мутация происводится, если 0 изменяется на 1, а 1 изменяется на 0, тогда ген становится потомком.

3.3 Лучшие хромосомы, найденные в родительской популяции, и имеющие вероятность репродукции Pr становятся потомками в новой популяции.

3.4 Если лучшая хромосома в дочерней популяции удовлетворяет требованиям создателя тестов, или количество генераций достигает макимума, тогда эволюционный процесс останавливается. Иначе, число итераций увеличивается на 1, и цикл продолжается, начиная со 2го пункта.

4. Остановка. Наконец, оптимальная хромосома является оптимальным решением проблемы выбора решений.

3: Генетический алгоритм Деба в стратегии выбора элементов.

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

Дополнительный параметр ГА.

Применяя ГА Деба в стратегии выбора элементов, параметры ГА по прежнему используются для доказательства качества выбора. Это такие параметры как:

  1. t – префикс, использующийся для дальнейшего определения.

  2. Ed – после кроссинговера расчитывается Эвклидово расстояние между двумя возможными решениями (P1, P2)

Основные различия стратегии выбора элемента по сравнению с ГА заключаются в следующем:

  1. Расчет фитнес-функции

    , номер элемента, удовлетворяющего условиям:

    или

    fmax – самое маленькое значение целевой функции приемлемого решения. Если нет приемлимого решения , то fmax = 0.

  2. Расчет кроссинговера.

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

    1. Когда встречаются 2 приемлемых решения, выбор зависит от правила

      ЕСЛИ (Ed пороговая) ТО выбирается решение с наименьшим E(Xk),

      ИНАЧЕ предыдущее решение комбинируется с приемлемым для получения Ed

         ЕСЛИ (Ed пороговая) ТО выбирается комбинированное решение,

         ИНАЧЕ выбирается предыдущее решение.

    2. При выборе между приемлемым и неприемлемым решениями, выбирается приемлимое.

    3. При выборе между двумя неприемлемыми решениями, выбирается то, которое нарушает ограничения в меньшей степени.

4: Дополнительный ГА в стратегии выбора элементов.

Дополнительный ГА (ДГА) стратегии выбора элементов изменяет параметры Деба, включая такие параметры как Эвклидовое расстояние и алгебра префиксов. Основное же отличие заключается в следующем.

Применение 2х точечного кроссинговера в турнирном выборе для выбора одного из двух элементов. Метод сравнения заключается в следующем:

  1. когда 2 приемлемых решений сравниваются, выбор будет зависеть от метода выбора.

    ЕСЛИ (t < tпороговая) ТО

       ЕСЛИ (Ed пороговая) ТО выбирается решение с наименьшим E(Xk),

       ИНАЧЕ предыдущее решение комбинируется с приемлемым для получения Ed

  2. При выборе между приемлемым и неприемлемым решениями, выбирается приемлимое

  3. При выборе между двумя неприемлемыми решениями, выбирается то, которое нарушает ограничения в меньшей степени.

5: Оценка эффективности

Поскольку линейное планирование применяется, чаще всего для поиска решения оптимизированной задачи, в данной работе сравнивалась эффективность SGA, Деб, AGA и нейронных сетей, расчеты нового линейного планирования (ЛП) [20] служат в качестве ссылки для экспериментальные результаты ЛП. Мы закодировали симуляцию виртуального банка, содержащего 1000 3х параметрических элементов и ограничений. Значения параметров и атрибутов в условиях были сгенерированы случайным образом равномерно распределенным по области их значений. Для сравнения эффективности предложенного метода, в соответствии с ограничительными условиями, основные настройки параметров ГА совпадают с параметрами ЛП. Эти параметры описаны в таблице:

Количество вопросов в банке 1000 элементов
Количество вопросов в тестовой последовательности 40 элементов
Эволюционная алгебра 1000 алгебра ' 1500 алгебра
Информационная емкость целевой функции 100 элементов на одиночной, и двойной. каждый для 5 различных возможных уровней
Параметр иерархического ГА Edпороговая = 6, tпороговая = 75
Хромосома 100
Вероятность кроссинговера 80%
Вероятность мутации 10%
Вероятность репродукции 10%
Ограничительные условия Более 10 параметров

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

Если в банке содержится 1000 вопросов и 40 элементов должны быть выбраны, ограничительные условия: 10+5+6+1+1000 = 1022. Таким образом, выбранные элементы должны удовлетворять 1022 условия. Используя различные ГА, тестирование проводилось 10 раз и была достигнуто средняя сумма квадратичных отклонений.

Результаты исследования:

  1. значения отклонений в SGA, Деб, AGA и нейронных сетях меньше, чем в ЛП.

  2. значение отклонения в АGА достаточно хорошее. По сравнению с ЛП среднее значение находится на уровне 99,96%.

6: Выводы и рекомендации

В данной статье мы показали эволюционную методику простого ГА, параметр разработки стратегии и провели «множественные ограничительные условия» в стратегии выбора элемнов. Кроме того, были оценены возможность реализации и эффективность. В соответствии с результатами исследования, были подготовлены следующие выводы:

  1. Алгоритм, использующийся в данной статье эффективно решает проблему «множественных ограничительных условий» в стратегии выбора элементов. Минимальное значение отклонения достигается для обеспечения более практичной методики, которая дает улучшенное качество теста, что является приемлемым для составителя.

  2. В общем, простой ГА нуждается только в фитнес-функции, и при этом не требует другой дополнительной информации. Таким образом, он может использовать различные состояния фитнес-функции и сохранить компьютерные ресурсы, чтобы избежать сложных математических расчетов. Основываясь на простом ГА К.Деб скомбинировал эволюционную методику. Была улучшена «стратегия параметров». Значение Эвклидового расстояния было использовано для добавления универсальности и улучшения приближения «параметра» (как можно ближе к оптимальному). В течении эволюционного процесса, проблемы выбора элементов были успешно решены и в значительной мере снижено отклонение между информационной функцией построенного теста и целевой информационной функцией. По сравнению с новой методикой ЛП, эксперименты показывают, что АGA дает лучшие результаты. Среднее значение находится на уровне 99,96%. Метод К.Деба показывает значение, равное 62,12%. Генетический алгоритм используется не только в рамках «ограничительных условий», он так же является более эффективным практическим инструментом.

Список литературы

  1. Ackerman, T. (1989). An alternative methodology for creating parallel test forms using the IRT information function. The Annual Meeting of the National Councilfor Measurement in Education, San Francisco.

  2. Baker, F. B., Cohen, A. S., & Barmish, B. R. (1988). Item characteristics of tests constructed by linear rogramming. Applied Psychological Measurement, 12(2), 189-199.

  3. Bramlette, M. F. (1991). Initialization, mutation and selection methods in genetic algorithms for function optimization. In R. K. Belewand L. B. Booker, eds., Proceedings of the Fourth International Conference on Genetic Algorithm, Morgan Kaufmann.

  4. Toroslu, H. T. & Arslanoglu, Y. (2006). Genetic algorithm for the personnel assignment problem with multiple objectives . Information Sciences, (in press).

  5. Deb, K. (2000). An efficient constraint handling method for genetic algorithms. Computer Methods in Applied Mechanics and Engineering, 186(2-4), 311-338.

  6. Deb. K. (2001). Genetic Algorithms for Optimization. (Rep. No. 2001002). India: Department of Mechanical Engineering Indian Institute of Technology Kanpur, Kanpur Genetic Algorithms Laboratory(KanGAL).

  7. De Gruijter, D. N. M. (1990). Test construction by means of linear programming. Applied Psychological Measurement, 14, 175-181.

  8. Deb, K., Pratap, A., Agrawal, S., & Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA–II. IEEE Transactions on Evolutionary Computation, 6(2), 182–197.

  9. G. Levitin, (2005). Weighted voting systems: reliability versus rapidity. Reliability Engineering & System Safety, 89(2) pp. 177-184.

  10. Hambleton, R. K., & Swaminathan, H. (1985). Item Response Theory: Principles and Applications. Hingham, MA: Kluwer, Nijhoff.

  11. Lord, F. M. (1977). Practical applications of item characteristic curve theory. Journal of Educational Measurement, 14, 117-138.

  12. Luecht, R. M., & Hirsch, T. M. (1992). Item selection using an average growth approximation of target information functions. Applied Psychological Measurement, 16(1), 41-51.

  13. Metcalfe, T. S., & Charbonneau, P. (2003). Stellar structure modeling using a parallel genetic algorithm for objective global optimization. Journal of Computational Physics, 185, 176.

  14. Papadimitrion, C. H., & Steiglitz, K. (1982). Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Inc., NJ:Englewood Cliffs.

  15. Sanders, P. F., & Verschoor, A. J. (1998). Parallel Test Construction Using Classical Item Parameters. Applied Psychological Measurement, 22(3), 212-223.

  16. Stocking, M. L., & Swanson, L. (1993a). A method for severely constrained item selection in adaptive testing. Applied Psychological Measurement, 17(3), 277-292.

  17. Stocking, M. L., & Swanson, L. (1993b). A model and heuristic for solving very large item selection problems, Applied Psychological Measurement, 17(2), 151-166.

  18. Sun, K. T. (1999). An Effective Item Selection Method by Using AI Approaches. Advances in Intelligent Computing and Multimedia Systems, 137-142, Baden-Baden, Germany.

  19. Sun, K. T. (2000a). A Genetic Approach to Parallel Test Construction. International Conference on Computers in Education 2000, pp.83-90, The Grand Hotel, Taipei, Taiwan.

  20. Sun, K. T. (2002). A Genetic Algorithm for Parallel Test Forms (Rep. No. 00101). Taiwan, Tainan: National Tainan Teachers College, AI & ICAI Lab.

  21. Salcedo-Sanz S, Bousono-Calzon C, Figueiras-Vidal AR (2003) A mixed neural-genetic algorithm for the broadcast scheduling problem. IEEE Trans Wirel Commun, 2(2), 277-283.

  22. Theunissen, T. J. J. M. (1985). Binary programming and test design. Psychometrika, 50, 411-420.

  23. Tsai , H. K. , Yang , J. M., Tsai, Y. F., and Kao, C. Y. (2004). A genetic algorithm for large traveling salesman problems. IEEE Transactions on Systems, Man and Cybernetics – Part B , 34 , 1718-1729.

  24. van der Linden, W. J. (1998). Optimal assembly of psychological and educational tests. Applied Psychological Measurement, 22(3), 195-209.

  25. van der Linden, W. J., & Boekkooi-Timminga, E. (1989). A maximum model for test design with practical constraints. Psychometrika, 54, 237-247.

  26. van der Linden, W. J., & Reese, L. M. (1998). A model for optimal constrained adaptive testing. Applied Psychological Measurement, 22(3), 259-270.

  27. Wightman, L. F. (1998). Practical issues in computerized test assembly. Applied Psychological Measurement, 22(3), 292-302.

  28. Wright, B. D., & Douglas, G. A. (1977). Best procedures for sample-free item analysis. Applied Psychological Measurement, 1, 281-295.

  29. Wright, B. D., & Stone, M. H. (1979). Best test design. Chicago: MESA.

  30. Levitin G.. (2006). Genetic algorithms in reliability engineering, Reliability Engineering & System Safety, 91(9), 975-976.