The multitude of the technology-based tools used for educational purposes is now a common thing to be seen. These tools can help within the educational process either for the organizational purposes or these are included in the materials used in education. This paper presents Kromatine, a generator of assessment tests which are obtained using a genetic algorithm, which includes it in the first category, organizational purposes. The genetic algorithm uses basic genetic operations and structures and it is presented in a form of a web application. It eases the organizational tasks of the teacher by giving him the opportunity to generate tests that will be used further in assessment. The questions are stored in a database and the user has the possibility to add questions to database and to generate tests that can be used later. The questions are characterized by a degree of difficulty and are multiple-choice type. The choice of the genetic algorithm is due to the fact that the problem can be summarized in generating an arrangement of question summing a given total degree of difficulty (comparable to the subset sum problem), which includes the issue in the category of NP-complete problems. Also, the problem structure can be easily modeled based on a general genetic algorithm structure.
As technology advances more and more and the modalities of easing organizational
tasks are more numerous and following several recent breakthrough researches. All
these research is based on nature functionalities and structures. Also, education is an
extremely important field within the domains of the people, from the primary school to
adult training [
We will present in this paper a primary version of a tool that generates tests used for assessment based on a genetic algorithm. As we will see, the questions are multiplechoice type and are selected from a database which is built overtime. Section 2 introduces a theoretical base formed from notions and operations used to build the tool. In section 3 we will present the actual implementation of the tool, in the form of a web application, and section 4 contains an example of obtaining assessment tests using this tool. 2
Genetic algorithm theory is rapidly developing due to advances in technology and research. Known for their large applicability, their approximate nature is a both a feature and a drawback that is currently studied in order to increase the accuracy of the solutions obtained. Thus, state of the art research on genetic algorithm is aiming to solving both classical theory problems and unusual particular issues.
Given the first direction, the applicability of the genetic algorithms to fuzzy
problems is a candidate for solving matrix problems (implying chessboard-like structures
such as the queen problem [
The problem studied in this paper is part of the second set of problems. Given the
fact that the problem of generating tests formed of question with a given requirement
is not a common issue found in the literature, the existing papers which deal with the
problem deal with the problem of efficiency of genetic-based generation [
Another issue regarding the studied problem is that this can be classified as
NPcomplete, due to its reduction to the subset sum problem, of generating subsets of finite
cardinal whose sum of difficulty degree is close to a given parameter, which is known
for being NP-complete [
Issues regarding the generation of tests which are secondary in this paper are also
consisting in the type of the question that is generated, whose number can be extended
using existing methods based on word analyze and NLP algorithms [
Finally, the problem described in the paper is a new integration of technology tools
within the vast domain of education. We should not exclude the social part of the
education [
Before the actual presentation of the tool to be made, we will present the notions that led to its creation. The tool has been developed based on a genetic algorithm, meaning that the structures used are the gene and the chromosome. Also, the questions and the generated tests are stored in a database. The definitions that follow present the particular notions and clarify the terminology used in this paper. The database has four tables which are basic for the needs of the generator: ─ table Questions, which contains fields storing the identification number of the question, the statement, the number of choices, the degree of difficulty of the question, the correct choice(s) and the user who proposed it; ─ table Choices, which contains the question identification number, the choice letter from „a‟ to „z‟ and the choice text; ─ table Tests, containing fields storing the identification number of the test, the questions, the total degree of difficulty of the test, the user who generated it, the generation timestamp and the generation time. The latter field is used entirely for monitoring and research purposes; ─ table Users, containing fields related to the user who uses the generator, such as user identification number or alias. The table is designed to store user data and has an organizational purpose.
A detailed perspective on the database tables is presented in Table 1.
The structure of the database DBQ containing the tables and the connections between them is presented in figure 1.
Specification 1. A question q (id; st; dd; V) is an object formed of the next components: ─ the identification number of the question id; ─ the statement st; ─ the degree of difficulty dd, dd ϵ {1, 2, 3, 4, 5}; ─ choices set V.
Observations:
The degree of difficulty dd is subjective for each question and it is considered to be input data given by a human operator. This degree is considered to situate on a scale from 1 to 5, where 1 is the least difficult and 5 means the most difficult. In order to normalize the difficulty and cancel to a certain extent the subjectiveness of the appreciation of the difficulty, a short explanation is given to the users.
The set V contains objects structuralizing a choice vi (id; l; cst), i = 1, |V| of the question, as follows: • question identification number id; • choice identification particle l. We choose as choice identification letters from the English alphabet, thus l ϵ {„a‟, „b‟, …, „z‟}. The number of choices is thus limited to 27; • choice statement cst.
Observation: a) A test T (S, GD) is a set of questions qi, i= 1, |S|, where S is the set of questions that form the test and GD is the degree of difficulty of the test:
Specification 2. Given the database question set Q and the selected test question set S for a given set of input data, a gene gi is an integer particle and a member of the set {1, …, |Q|}, i ϵ {1, …, |S|}.
Observations: a) Basically, a gene stores the order number for a question (g is equivalent to qid). b) |S| is an input data and used in the algorithm. c) The elements of set S are unknown before the generation, being an output data.
Specification 3. Given the database question set Q, the selected test question set S at a given state, the population set NC and the desired total degree of difficulty MGD, a chromosome C is an object formed of: - order number id, id ϵ {0, …, |NC|}; - the gene set Gj = {gi | i ϵ {1, …, |S|} }, where G = S; j = 1, |NC|; - the fitness function f defined as follows (1) Observations: a) Gj is equivalent to qid. b) We can easily observe thatMGD= [|S|,5×|S|]. c) The fitness function checks if the sum of the difficulty degrees of each question within a chromosome are lower and as close as the value MGD. d) The chromosome contains the order numbers of questions that form a test. If we denote the test questions set by T, then T = S = {Gi| i = 1, |S|}.
Proposition 4. Given a chromosome Ci (i = 1, |NC|) and random positions a and b (a, b = 1, |S|), the mutation operation is defined as the shift of the genes found on the positions a and b.
Observation. The mutation has as result the generation of a new chromosome.
Proposition 5. Given two chromosomes Ci and Cj and a random position p, the crossover operation is defined as a succession of steps as follows:
─ The two chromosomes are split at the position p. ─ The first part of the chromosome Ci is combined with the second part of the chromosome Cj and the first part of the chromosome Cj is combined with the second part of the chromosome Ci. ─ Two new chromosomes Ci’ and Cj’ are obtained, as follows: ′ = ( 1, 2, … , −1, , … , )
(3) ′ = ( 1, 2, … , −1, , … , ) (4) Within the algorithm, the order of the operations is:
Generation of the initial population Sort of chromosomes based on fitness Mutation of chromosomes
Crossover of chromosomes
Operations b), c) and d) are repeated for a previously-set number of generations. The final result is a list of tests from which we store a finite number of tests which have the highest value of the fitness. 4
The implementation was made in the form of a web application. The implementation was based on Bootstrap framework, used for display and structural components. The back-end component is based on PHP combined with MySQL used for database storage. The customizable parameters, i.e. the ones which influence the performance of the final output (the size of the initial population, the mutation rate, the crossover rate) can be modified, but they have default values that guarantee a close-to-optimum solution. Thus, if the user in unaware of the definition of these parameters, he can as well ignore giving them values. Regardless the situation, the technical details are presented in a help section.
The main page of the application is shown in Figure 2 (a-d).
The application was built of the following components: ─ the dashboard, which shows a summary of the user activity; ─ the script for proposing questions, consisting in an extended form; ─ the page for generating questions, which is the core of the entire application and where the input data is set; ─ the page used for showing the generated tests for a given user, where he can choose some of the tests generated before.
The visual representation of the application scheme is presented in figure 3.
The presented application is basically a core for a future development of an assessment
aid tool for a teacher. The implemented tool can be in this matter included in a long list
of technology-based tool that are used in education, widely developed [
The educational process depends on mathematical parameters that technology can use in order to ease the organisational tasks for the person who is in charge with the educational process (e.g., the teacher). Also, the technology has implications on the actual educational process by providing materials that create an interactive learning environment.