Improved modeling of intelligent tutoring systems using ant colony optimization

“Intelligent tutoring system”(ITS) is a broad term, encompassing any computer program that contains some intelligence and can be used in learning (Mustafa and Mohamed 2011). Intelligent tutors offer relevant educational activities and provide feedback on those activities based on the learner’s profile (Schiaffino et al. 2008). Identification of the learner’s particular profile is the first phase of adaptation. The basis of didactical methods in intelligent tutoring systems is called the Learner Model. The Learner Model stores information concerning individual learners (especially the current knowledge state of learners). The Learner Model is a set of parameters containing the information about a learner’s personality, experience, and education. It is important that each system is adaptive to a user.

Domain knowledge contains learning contents. The material presentation component enables presentation of learning content in different ways according to learner characteristics, on the basis of the regularly updated Learner Model. Data mining has a key role in adaptive models. By using intelligent analyses, it is feasible to connect particular concepts and content with student characteristics (i.e. learning styles). The user interface is responsible for creating the link between the learner and the system, without which no effective connection is established. The purpose of this module is to use peripheral devices to provide the student with necessary information and to receive his/her responses (Grasha 1984).

Adaptive educative systems try to offer an alternative to non-individualized approaches by providing several services adapted to the learner’s profile. The goal of such adaptation is to maximize the subjective learner’s satisfaction, the progress of learning, and evaluation results. For this strategy, there are three parts implemented in ITS:

“Learning style” encompasses everything that is characteristic to an individual when she/he is learning: i.e. a specific manner of approaching a learning task, and/or the learning strategies activated in order to fulfill the task. According to a learning style represents, the composite of characteristic cognitive, affective, and psychological factors that serve as relatively stable indicators of how a learner perceives, interacts with, and responds to the learning environment (Keefe 1979). Landry claimed that “everyone has a unique learning style, and instruction should be designed to best accommodate different methods of learning.” (Landry 2011). Each of the learning styles offers a set of principles and recommendations for the instructional strategies that should be used with the students pertaining to each category. Most psychologists recommend that the teaching style of the instructor should correspond to the learning style of the student (the “matching hypothesis”). Felder mentions that mismatching can have serious consequences: students may feel “as though they are being addressed in an unfamiliar foreign language. They tend to get lower grades than students whose learning styles are better matched to the instructor’s teaching style and are less likely to develop an interest in the course material” (Felder 1993). Dunn and Griggs (2003) also suggest that teachers adapt the instruction and environmental conditions by allowing learners to work with their strong preferences and to avoid, as far as possible, activities for which learners report having very low preferences.

The broader concept of style has been linked with notions of learning style (Dunn and Dunn 1978), psychological type (Myers and McCaulley 1985), cognitive style (Kirton 1987; 1994), and, more recently, to problem-solving style (Selby et al. 2004a) is defined as consistent individual differences in the ways students prefer to plan and carry out generating and focusing activities in order to produce ideas and prepare for action.

There are many models for detecting learning styles. Some learning style models that we have gathered include those of Paramythis and Loidl-Reisinger (2004), Kolb, Felder and Silverman (1988), Dunn and Dunn (1978), Myers-Briggs Type Indicator (MBTI). (VARK) styles the visual, aural, reading/writing and kinesthetic (Flemming 1995). Due to space limitation, we shall not elaborate on each of these learning style models, but only discuss those that are significant to our work.

In adaptive educational systems, the content of courses is tailored to the individual differences of learners by using a set questionnaire to determine the learner’s learning style and then adapting their material presentation according to that style. As far as the creation of the learner model is concerned, Pham and Florea (2012) presented a concept that classifies modeling methods for learners as explicit and implicit modeling methods. Explicit modeling is a simple and straightforward method for inferring learners’ learning styles. In this method, a dedicated measuring instrument (e.g. psychological questionnaire) is used in association with the learning style model. This method is labelled “explicit” as it requires direct input on the part of the student, who has to explicitly specify her/his learning style by filling in the questionnaire. In this way, a static learner model is created at the beginning of the course and stored permanently. Some disadvantages of this model are that:

There is another method, which uses an implicit and/or dynamic modeling method. This method is based on already available feedback information, as well as the learners’ interactions with the system. It determines a corresponding learning style without having to ask for additional effort from the part of the students. This may also have the advantage of being more accurate, overcoming the psychometric flaws of the traditional measuring instruments. Additionally, a dynamic modeling approach can be envisaged, with the learner model continuously updated during the learning process (Popescu 2008).

A learning object (LO) is an independent content component that can function as the learning content of a course module. It can be defined as any digital content resource that supports learning that can be re-used and delivered on demand across the network. Examples of larger reusable digital resources include entire web pages that combine text, images, and other media to deliver course modules (Schreurs and Moreau 2006). The IMS Global Learning Consortium, the advanced distributed learning (ADL) co-laboratory, and others (MASIE Center 2002) have produced learning objects in their standardized works. Currently, the international Sharable Content Objects References Model (SCORM) (ADL 2004), based on the results of work done by the above-mentioned groups, is widely used in e-learning ecosystems. Many learning materials, such as multimedia, images, slides, or others components, may be packaged and placed in learning objects by SCORM. Thus, these related learning objects can be reorganized according to the sequence of a course (ADL 2004; IMS 2003), Furthermore, when learning content is to be created, organized, and placed in the sequence of a learning course, this sequence is similar to the path of that course. Accordingly, many web-based intelligence tutoring systems have developed sophisticated solutions for customizing learners’ learning needs for meaningful learning relationships (Wang et al. 2008). An optimal adaptive learning path will help the learners reduce cognitive overload and disorientation, thereby improving the efficiency of the Learning Management System (LMS). Ant Colony Optimization (ACO) is a widely accepted technique as it provides an adaptive learning path to the learners. (Pushpa 2012)

An ant colony algorithm is a group of optimization algorithms inspired by ants exploring for food. Ants spread pheromones on the paths they navigate when finding food and returning to the nest. The first ant system (AS) was proposed by Dorigo (1992) and was successfully applied in tackling the wellknown traveling salesman problem (TSP) (Dorigo and Gambardella 1997). It is based on ant behavior when finding the shortest path between a food source and the nest. A single ant lays is equal pheromone and heuristic information to mark trails. When the paths are ranked by other ants, some of the trails may be reinforced and others paths may be allowed to evaporate. A trails’ pheromone can be observed via the number of ants passing through the trail. An iterative local search algorithm tries to link the current paths to neighboring paths until a better solution is found. This meta-heuristic is inspired by the collective behavior of storing and path-tracking observed within ant colonies (Dorigo and Stützle 2004). Figure 1 shows the pseudo code of ACO.

Ant Colony Optimization (ACO) is a widely accepted technique since it provides an adaptive learning path to the learners. Meta-heuristic which is used in intelligent tutoring systems provides the learning path in an adaptive way. The most interesting feature of ACO is its adaptation and robustness in an environment where the learning materials and learners are changing frequently (Pushpa 2012). (Ghusoon et al. 2013) Propose a new dimension to detect learning styles, which involves the individuals of learners’ social surrounding such as friends, parents, and teachers in developing a novel agent-based framework. The multi-agent system applies ant colony optimization and fuzzy logic search algorithms as tools to detecting learning styles. Pushpa (2012) presented the existing ACO approaches towards providing an adaptive learning path and an introduction towards an enhanced attribute ant for making the e-learning system more adaptive. Sharma et al. (2012) proposed an ant-based algorithm called Adaptive Content Sequencing in eLearning (ACSeL) for providing learning content to online learners. The algorithm evaluates the level of a learner and recommends appropriate concepts to him/her. It is sensitive to the changes in learning behaviours of each learner and fine-tunes its strategies to recommend the next concept accordingly. The behaviours of past learners are captured and utilized to recommend content to prospective learners. Wong and Looi (2009) propose the Dynamic Learning Path Advisor (DYLPA), a set of course sequencing algorithms that combine both prescriptive navigation rules and an inductive mechanism. Also utilizing the ACO technique, the Style-based Ant Colony System (SACS) (Wang et al. 2008) categorizes alumni into four learning styles (visual, Aural/Auditory, Read/Write or kinesthetic). In recommending the next node, the pheromones deposited by the alumni who fall into the same category with the target learner are favored in the computations. The pheromone computation is not based on alumni performances, but merely the number of times the alumni have traveled. Gutiérrez et al. (2006) proposed a similar ACO-based approach. In their approach, sequencing graphs record the frequencies and the performances (“successful” or “failed”) of various paths that other learners have tried. The information is presented to the target learner every time he/she finishes a learning unit (a “node” in our context), so he/she can choose the next unit by referring to how all peers performed (i.e. the numbers of successful and failed peers) in the same situation. Van den Berg et al. (2005) developed a simplified ACO algorithm that only keeps the records of the paths selected by the learners who have successfully completed the course, as determined by a post course 5-question multiple choice quiz, by maintaining a transition matrix that records the number of learner transitions between individual pairs of nodes on such paths. The full path is then recommended to the next learner using the roulette wheel mechanism. Paraschool (Semet et al. 2003) applied the ACO heuristics to a pedagogic material navigation problem on e-learning, and experimented with an “ant-hill” method which laid the pheromone depending on how students validated an item (success or failure), so as to optimize learning paths with different students that have different views. Therefore, the ACO method seems well suited for tackling adaptive learning in a dynamic learning environment.

At the beginning, a learning object is randomly assigned to each ant. At every stage of constructing the learning path, the k-th ant uses a probable selection law system called randomized comparative law in order to select the next learning object. The probability of the k-th ant being located on LO_i and wanting to select LO_j is calculated in Eq. 2.

In this equation, N _i ^k is the series of learning objects allowed to be selected at each stage, showing the sequence and priority of learning concepts. η _ij is heuristics information, τ _ij is the pheromone trail, and α and β are parameters that indicate the relative importance of the pheromone trail and heuristics information in selecting the next learning object.

Heuristics information, as defined in this algorithm, is derived from the SACS algorithm. However, the formula defined in this study is fitted to be closer to the values of the forgetting curve. η _ij  = R _ij is a heuristics value which is inversely proportional to the time, and is derived from the unit-time learning forgetting curve (Ebbinghaus 1913) that continuously represents the decline in the learning data of the learner. The memory coefficient (R), which represents the learning loss over time, is shown below using a descending exponential function and two constants of s and ʎ to adjust to real learning situations:this equation, t _ij is the time duration between node i to node j, λ is the learning constant, and s is relative power of the memory which is proportional to the number of iterations of a subject. The greater value of R _ij represents the greater ability of a learner to recall the information contained in the i-th node when going to the j-th node.

When learning paths are constructed by learners, they are improved by a process of local search, Learners whose mean score along the path is in pass mode, and where the total time they have spent studying learning objects has not passed a certain limit, are considered to be the best ants, and are then selected so their experience can be used in the next iterations.

Selecting appropriate parameters to update the pheromone can play an important role in highlighting the paths in which learners are performing best. The performance indicators of learners in selecting a course concept include the completion of exercises in less time and achievement of higher scores. In the proposed algorithm, the amount of pheromone increase for each learner is dependent on three main parameters:

In this case, the j-th node is a course concept, the score and time taken to do an exercise are equal to zero, and only the value of R is considered. In each iteration, only the ants with the best results in a specified time interval (Best Ants) are allowed to add pheromone. This value is defined as follows:

In this equation, Δτ _ij ^k is the amount of pheromone that the k-th ant leaves on the edges it had crossed.

In this equation, S _ij ^k is a score that the k-th learner has earned and T _ij ^k is a time that has been spent on studying c _i and doing the exercise e _j . S _max is the highest score by all learners that have already passed the edge (i, j). L _k is the learning path traveled by the k-th ant.

In this algorithm, the idea of similar ants expressed in the SACS algorithm (Wang et al. 2008) has been used to follow the paths that are most accommodating with learners’ traits in terms of learning and problem-solving styles. Pheromone changes for using adaptive learning rules on the edges (i, j) are as follows:where Δτ _ij ^k,style (t) and Δτ _ij ^k,rank (t) are variable amounts of pheromone left on the edges (i, j) from the time t-1 to the time t, the former indicating changes in pheromone by ants that have a similar learning style with the k-th ant. ϑ is the number of learners with the same style, representing changes in pheromone of all the ants regardless of their style. σ is the number of learners that have crossed the edges (i, j).

To update the pheromone trails, some pheromone is subtracted from all edges by an initialized constant, then spread over the edges that the best learners have crossed in their learning paths. Pheromone evaporation in this algorithm is implemented by the following formula:

In this equation, ρ is the pheromone volatilization rate per unit of time (0 < ρ < 1). After performing volatilization, the best ants leave pheromone trail on the edges that they have crossed on their own learning path.

The main role of heuristic information is to avoid constructing responses with poor quality. In the SACS algorithm, based on the ACO, the value of the heuristic function is obtained from the equation:

This is a relation to indicate the forgetting curve. The R _ij curve behavior, which was improved in the previous research by the dynamic parameter c, is still far from the actual values of the forgetting curve. However, it still does not coincide, completely forgetting curve values. In this paper, this function is fitted to Eq. (3), by reasons given in the section (6.1).

Despite the effectiveness of meta-heuristic algorithms such as ACO in solving decision-making and optimization issues, this algorithm requires high precision while carrying out the tests. Improper adjustment of algorithm parameters causes reduced efficiency and effectiveness. In the proposed algorithm, the most efficient method for adjusting the parameters is one which considers the entire space. for solutions at the beginning of the search. It identifies all possible learning paths and moves towards optimal trails. Two types of local or global optimality may occur here. To determine the behavior of the proposed algorithm and the effect of the proper adjustments of the parameters on the overall behavior of the algorithm settings, different experiments were designed to examine the impact of heuristic information β, Pheromone trails α, and Pheromone evaporation rate ρ. Information on these experiments is presented in Table 2 and Fig. 4 shows the relationship between dynamic parameters ρ, β and t.

In this experiment, the proposed algorithm was implemented using MATLAB software. The behavior of ants (learners) was simulated, and the choice of input data, such as the time between selecting two learning objects (t), total time spent on study and problem solving (T), and the attention and skill of every learner (js), was done from a database randomly generated in a large volume with normal distribution. Score prediction was carried out based on the results of Hong study (1998). Then, given that the new system is a development of the previous system, the previous system was considered as part of the current system in comparing the two algorithms. This means that it is assumed that the previous system’s learners are the learners of the new system, for whom parameters related to time t, T, as well as scores of recitation (score) during learning activity are registered in their profiles. Now the algorithm for updating pheromones will act in two ways. In the first method, it acts in accordance with the SACS algorithm, and only the parameter “t” will be used as input of the pheromone update formula, thus determining the learning paths. In the new method, initially, a local search procedure will be applied for finding the best learners, and then the parameters of t, T and score will be used to update pheromones. This experiment was carried out for the initial population of 50 ants and in 2000 iterations for two algorithms. Learners’ performance results in optimal path are shown in the section (6.3).