A modified ant colony algorithm for personalized learning path construction

Abstract

An e-learning system offering a personalised learning path will be vastly appealing to the learners. Adaptive techniques when employed in e-learning can sustain the interest and motivation of the learners and help them to complete the enrolled courses successfully. In addition, it would improve their performance and thus, enhance the overall learning experience. Personalisation takes into consideration the characteristics of the individual learner and the diversity in his/her needs. The main challenge is finding a match between these individual characteristics and the sequence of the learning content. It is a complex task to implement as it involves selection of the appropriate material from a vast amount of the available learning materials. It is a challenge to perform this process manually as it requires both technical savvy and pedagogical skills. In this paper, a stigmergy model is proposed, which was applied to build a customised learning path. The aim was to provide personalisation that satisfied the needs of an individual in a widely heterogeneous e-learning environment. Compared with the traditional teaching method, this tailored learning path, generated using the proposed approach, shows promise and was found to enhance the performance of the learners.

Keywords

Learning path learning content sequence personalised E-learning ant colony optimisation curriculum sequencing

1 Introduction

An e-learning environment has a huge drawback of limited personal support from instructors, thus relying on self-support and self-guided learning. New learning materials are made available regularly, and result in the overwhelming of resources. This may cause overloading learners with too much of irrelevant information and confuse them [1]. Thus, an personalised system should support learners in the absence of tutors and guide them by offering only the relevant information. This can be achieved by offering personalised learning environment catering individual needs.

Researchers have emphasised the importance of personalised learning to improve performance and learning efficiency [2 –4]. Unfortunately, most of the improvements in e-learning has been channelled in incorporating evolving technology; leading to technology driven e-learning [5]. It is dominated by Learning Management System (LMS) which has tools to support communication, collaboration, teaching and learning process, but they neglect the individual differences of learners.

A personalised e-learning system provides a way to customise content according to learner’s requirements. It adapts to the needs of the learner with an intent of enhancing the effectiveness of learning. As each learner differs in the way he acquires and assimilates knowledge, personalised e-learning environment provides the possibility to tailor the content incorporating the individual differences.

In e-learning context, personalisation supports two types of adaptation: adaptive presentation and adaptive navigation support [6]. In adaptive presentation, contents of the page are modified presenting different contents to different learners. The information is customised according to learner’s interest or knowledge instead of delivering the same contents to all learners. Say, for instance, beginners can be supported with supplementary materials whereas, experts will be provided with detailed and deeper information [7]. Also, the difficulty level, media, the length of the content is varied with learner. Adaptive navigation support provides adaptive links guiding different users to relevant information [8].

Presentation of learning contents and availability of navigation links in an adaptive way may support the learners in many ways like enhancing motivation, retaining the interest. They can present only content in the right media, with right level of difficulty such that presented materials can be understood. But, this approach does not guarantee the achievement of learning goals [9]. In addition, the presentation of content in a page and the available navigation links will be different at each visit; it may lead to unfamiliarity and confusion. The learning path encompasses guide steps for learners to construct knowledge, skills and achieve their goal [10].

Learning path is the organisation of learning contents in a certain way such that the learning objectives are met. It defines the learning process in a course by providing only with the needed information at a specific time and also it establishes how a learner will learn, thus has a major part to improve learner’s efficiency [11]. Due to the inadequate support from the tutors in the e-learning environment [12], personalised learning path would help, especially the lifelong learners to achieve goals in an efficient manner.

The challenge of personalised learning path lies in choosing appropriate contents and arrange them in the right order [13]. Learning path construction problem is about selecting appropriate learning contents and sequencing them in a way such that it supports learners to reach their goal. The process of personalised learning path construction has to be automated due to following reasons:

Manual construction of personalised learning path is labour consuming.

Instructor determined path can be prone to error.

Effectiveness and quality depends on instructor’s experience.

Abundant wealth of resources makes it difficult to find the right material to match individual needs.

Time consuming process.

However, few challenges need to be addressed in automatic construction of learning path.

Suitable learning resources: The purpose of teaching and learning is to instill and gain knowledge in a specific domain. This can be achieved by providing appropriate learning materials based on user needs.

Suitable sequence: The way how learning contents are sequenced determines how learners learn. The materials have to be sequenced in a way such that learner can build up new knowledge from the mastery of prior knowledge.

Most of the e-learning tools assume that all learners are similar; learn in the same way, thus implement a one-size-fits-all method. In this approach, all learners follow the same content, activities and sequence of materials irrespective of differing needs. Furthermore, e-learning environment promotes self guided learning and offers less support. The availability of vast amount of e-learning contents results in the abundant resources, making it difficult to choose the relevant one and confronts the naive user. Providing an optimal learning path satisfying the diverse needs of the learner is a key issue that needs to be addressed. Several approaches have been applied to the learning path problem in the last two decades. Existing methods on learning path construction formulate learning paths based on their characteristics like knowledge or learning style. This makes the e-learning systems to provide personalised content to individuals according to chosen traits. However, such a formulation is not sufficient and efficient enough. The main concerns on learning path construction include how to select appropriate contents for each topic, and maintain the relationships among them and delivery them in sequence. There is a need to construct learning path which can pedagogically design strategies based on learning objectives, generate learning resources adaptive to different students, and analyze the suitability of the material to the individual learner.

As there are several hundreds of resources (say n), there is a possibility of n! sequences. The complexity increases when learner characteristics and prerequisites are considered. Since learning path construction is a NP-hard problem, a stigmetry approach was proposed to construct personalised learning path according to individual needs. This approach delivers optimal learning path by

Incorporating experiences of other similar learners (alumni).

Extracting information pertaining to the emergent and collective performance of alumni.

Indirect social interaction – through the observation and deployment of traces left behind by alumni in an adaptive and dynamic learning environment.

The rest of the paper is organized as follows. Section 2 reviews the related work in learning path using Evolutionary Computing (EC) approaches. Section 3 describes the problem and scheme of representation. Section 4 details the stigmetry approach in constructing personalised learning path. Section 5 explains the experimental methods and discusses the results. Section 6 draws the conclusion.

2 Review on approaches to learning path construction

In the last few years, several approaches have been proposed and used to provide customised learning path. The following section discusses evolutionary computing methods used for creating a customised learning path.

Evolutionary Computing approaches have been explored in the educational sector. Researchers have experimented with it to solve highly complex optimisation problems like content sequencing, timetable scheduling and automated question generation. These approaches are nature inspired methods based on the natural metaphor. The natural insects like ants, fish, bird exhibit complex and coordinated behaviour with decentralized control and have natural intelligence in solving problems like finding the shortest path between food and nest(ants), thousands of birds fly in the space without colliding with each other. They are highly adaptive and have high awareness about the environment. Due to the growing size of e-learners, diverse nature of e-learners and vast amount of learning materials, evolutionary computing approaches are considered as one of the appropriate method to provide solution to the complex and evolving e-learning environment.

Semet et al. [14] applied ACO to select the suitable path. The course components are splitted into sub units and each sub components representing nodes. The connection between two nodes are established via arcs and have weights reflecting the suitability of the path. The value of the weight depends on pedagogical weight, visits made to that arc and success/failure. A fitness function calculates the probability of next node to study. The shortcoming of this approach is that suitable path, but with high difficulty level was never visited. To alleviate this problem, Valigiani et al. [15] and Gutierrez et al. [16] revised the fitness function of the previous study which did not produce promising results. Style-based Ant Colony System (SACS) [17], a modified ACO approach to find the optimal path was proposed. The pheromone strength depends on the frequency of the visits on that node by learners. Attribute-based Ant Colony System (AACS) [10] aimed to find the perfect association between learning materials and learners. Dynamic Learning Path Advisor (DYLPA) [18] put together two techniques ACO and perspective rules to select learning path. Kurilovas et al. [11] presented dynamic learning based on learning style. Kardan et al. [19] proposed adaptive learning sequence driven by Ausubel Meaningful Learning Theory. Micro-learning path recommendation based on improved ant colony optimization algorithm was proposed [20] where the recommended learning path will be reorganised according to the transition of learners’ knowledge level and change in learning goal.

Seki et al. [21] arranged the learning objects (LO) according to their attributes to construct learning scenario. The optimal learning sequence is selected by applying distributed Genetic Algorithm (GA) combined with multi-objective GA. Chen [1] used GA to deliver suitable learning paths for each learner. The fitness function was computed based on learner ability, difficulty level of materials and concept continuity parameters. Hovakimyan et al. [22] constructed teaching scenarios from teaching materials based on GA. Samia and Mostafa [23] generated learning path using GA based on student profile and educational goal. Huang et al. [24] combined a genetic algorithm and case based reasoning based e-learning system to provide an learning path. A learning path recommendation system (LPRS) was proposed to recommend suitable paths based on learning styles and knowledge levels using variable length genetic algorithm [25]. Wan and Niu [2016] employed mixed concept mapping and immune algorithm for providing recommendation of paths considering it as a constraint satisfaction problem (CSP). Vanitha et al. [2019] combined ACO and GA in a collaborative manner to personalise learning path based on subject independent traits.

The learning path construction based on genetic algorithm generates learning path based on the individual characteristics. Though, it is generally considered a simple algorithm to implement, the challenging lies in the calibration and tuning of its several parameters. The performance of GAs is highly influenced by these parameters. Also, the quality of the solution depends on the selection of operators. Thus, improper choice of genetic operators may produce illegal learning path.

The learning path based on ACO techniques abstract away the individual properties of learners drawing efficient learning paths from the emergent and collective behavior of a of learners. Most of the studies on learning path construction based on ACO recommend learning paths that are frequently followed by alumni. These paths may not be the right learning paths for a learner. To achieve effective personalized learning path recommendation, there are three issues to consider. First, learners with similar characteristics to a given learner has to be identified, the path travelled by them has to be obtained instead of choosing the frequently or mostly travelled in order to avoid sheep flock effect. Second, learning performances of alumni should be incorporated into the computation rather than their learning paths. This is because the path most chosen need not necessarily be the most effective path. Third, the suitability of the LO in terms of difficulty level and time needed to complete it has to be checked against individual. Finally, there has been emphasis and demands on subject dependent traits like knowledge, preferences. In fact, learning progress is determined by several subject independent traits such as emotions. Especially in e-learning, learners often feel bored and disengage from learning and there needs a way to foster/neutralize their positive/negative emotions through learning contents. It has potential to influence the learning of the learners, affect their rational thinking and lead to success or failure depending on the emotional state.

There has been few works that constructs learning path using ACO. Learning path is the sequence of learning objects (LO). The novelty of the proposed work is how the next learning object is selected that closely matches learner’s characteristics. Most of the works have computed pheromone based on the number of times a specific path was followed by alumni. Secondly, we have implemented memory in each node that stores the learning objects that has been studied/visited and avoid loops. Thirdly, we have considered the time taken by alumni to study a LO which indirectly gives the difficulty level of that LO as heuristic information. This heuristic information has a part in deciding on the next suitable LO. Finally, we have used pheromone decay parameter to avoid unlimited accumulation of trails over some component and to forget the bad decision taken previously. A comparison table (SM-table 1: Comparison of ACO mechanism of the proposed work with similar studies) has been given as supplementary material indicating the differences in the features of ACO mechanism between our proposed approaches to existing approaches.

3 Stigmergy model description

In this paper, a learning path is viewed as the arrangement of learning objects in a particular order that aligns with learning objectives. The personalised learning path should enable learners to attain the goal and maximise their performance.

3.1 Problem formulation

Learning path construction can be seen as NP-hard problem due to vast amount of resources and various ways of combining them. LO can be a learning content, assessment exercise, quizzes. The problem of learning path is to select suitable LO based on emotion and cognitive ability. For each learner, emotional state from EEG [28] and cognitive ability are obtained. Each learner studies the LO and takes assessment as given in the sequence. Scores from the assessment signifies the performance. The objective is to find the match between learners and learning object in order to maximize the mean score,thus the performance of learners. Learning path can be presented as weighted graph comprising nodes, edges, weights on edges and ants. it is given as G=(C,E) where C is set of learning Objects (LO) and E represents arc connecting LOs. Each arc has value representing the pheromone. The pheromone intensity is computed based on the score obtained by students. The modeling of the problem with the concepts offered by ACO domain is given in Fig. 1.

Fig. 1

Artificial ant model.

Node represents Learning Objects and Ants are modeled as Learners (Alumni). The Edges are possible Pedagogical Sequence and Weights on edges are Pheromones. Each node has data structure to maintain the information needed to make decision. The transition from natural ants to artificial ants is shown in Table 1.

Table 1

Natural ants to artificial ants

Natural Ants	Artificial ants (Our model)
Habitat	Weighted Graph made up of nodes and edges
Nest &food source	Nodes constructed representing the start and destination of the graph
Pheromones	Performance of alumni (numbers on edges)
No Memory	Memory in the form of data structures to store relevant details.
Foraging behavior	Path in the graph guided by pheromone values

The artificial ant does not work exactly the same like a real ant. They are different in certain ways as given below.

Real ants leave trail of pheromone when they move in both directions (from nest to food source and from food source to nest). The ants of the present model leave trail on their way to reach the goal.

Movements of real ants are asynchronous, whereas, the movements of artificial ants are synchronous.

In real ants, the intensity of the pheromone depends on the distance between the nest and food sources, and back to the starting point, nest. The intensity of the trail depends on the performance of the students in this model.

3.2 Assumptions of the model

A few important assumptions made about this model are:

Sufficient number of learners who completed the learning path (alumni) are available at any given point of time.

Sufficient number of alumni similar to the current learner are available to guarantee the sufficient data to carry out this approach.

Alumni followed different paths to guarantee availability of several paths to choose from so that the algorithm converges to optimal solution.

Learner undergoes only one emotion at any given time.

Learner poses required knowledge level to study a LO.

The prerequisites for a given LO are known in advance.

The start LO and end LO is assumed to be same for all learners and are known in advance.

3.3 Description of learner model

In a personalised approach, learner attributes determine LO and thus the learning path. Each learner is represented as L; L={L₁, L₂, L₃ ⋯ L_n} and the following attributes are considered for each learner.

Learning Objectives: Represented as LOB; LOB={LOB₁, LOB₂, ⋯ LOB_n}.

Emotional State: Represented as E.

Cognitive Capability: Represented as C; C={C₁, C₂, C₃ ⋯ C_n}. It takes the value High or Low.

Performance: Score obtained in the formative and summative assessment and are recorded for each learner. Represented as P;P={P₁, P₂, P₃ ⋯ P_n}and has value between 0 and 100.

Thus, the learner model is constituted by 4 tuple. L= {LOB, E, C, P}.

3.4 Description of learning content model

A reusable, small chunks of e-learning materials are called learning objects. They are represented as LO; LO= {LO₁, LO₂, LO₃ ⋯ LO_n}. Learning content is modelled as 3 tuples; LO={D, T, PR} and are defined as follows.

Difficulty level of content. It is represented as D; D={ D₁, D₂, D₃ ⋯ D_n}.

Time. It is represented as T; T={T_i} where T_i is the time needed to complete the LO.

Prerequisite. It is represented as PR; PR={PR₁, PR₂, PR₃ ⋯ PR_n}. It indicates the prior learning materials needed to understand and complete before taking up this LO.

4 Methodology for learning path construction

This section discusses the construction of learning path using stigmergy model.

4.1 Proposed stigmergy model

Learning path is the right order of learning content and activities in order to obtain learning objectives. As learners are diverse in nature, there is a need for different paths according to his/her profile. A two-phase approach was adopted to construct the learning path as shown in Fig. 2.

Fig. 2

Two phase approach.

4.2 Phase I - Grouping similar alumni

In the first phase, similar alumni were grouped using genetic K-means algorithm and are discussed below.

4.2.1 Phase I: Learner Characteristics

Three characteristics were collected implicitly from learners when interacting with e-learning system. The emotion of the learner was detected from EEG. The working memory (WM) and cognitive load of the learner constitute the cognitive ability. The emotion detection and cognitive ability elicitation were not discussed as it is beyond the scope of this paper. Every characteristic was represented as binary value either 0 or 1. Sample data for the representation are shown in Table 2.

Table 2
Learner characteristics representation

Learner Learner Characteristics

Anger Anxiety Boredom Frustration Eureka Curious WMC Load

Present(1) /Absent (0) High(1) / Low(0)

Learner 1 1 0 0 0 0 0 1 1

Learner 2 0 0 0 0 1 0 0 1

Learner 3 0 0 0 1 0 0 0 0

Learner	Learner Characteristics
Learner 1	1	0	0	1	1
Learner 2	0	0	1	0	1
Learner 3	0	1	0	0	0

4.2.2 Phase I: GA K-means clustering algorithm

Grouping the learners based on their characteristics is the fundamental step in the proposed approach. Hence, the choice of clustering algorithm is vital. Firstly, it should produce a high quality solution without any need of inputs from user. Secondly, algorithm has to be computationally fast. We referred the research works listed in the SM-table 2: Overview of research works on integrating K-means and GA of supplementary material and adopted GA K-means proposed by Kim and Ahn [29] to produce high quality cluster in optimised time.

Reasons for choosing this approach are:

It is simple.

It is efficient compared to traditional clustering algorithm.

It is validated in a real world application, e-commerce application.

The algorithm produced a satisfactory results.

It is simple.

In the following section, the steps involved in clustering similar alumni have been discussed.

Representation of chromosome Each chromosome is made up of eight genes and is represented in binary format. Each gene is encoded to represent the learner characteristics. For example, learner 1 in Table 2 can be represented as binary chromosomes {1 0 0 0 0 0 1 1}.

Initialisation of Population Population size is an important criterion and is chosen based on the complexity of the problem. If it is set to a small value, it causes fast convergence; may not produce the best possible solution. On the other hand, if the population size is high, it guarantees an optimal solution. But, it will increase the time to find the solution. To balance this, a population size of 100 was chosen.

Fitness function Calculation The objective function represents the goal to be achieved and the fitness function was calculated using the Equation (1) as given in [29]. $F (x) = \sum_{j = 1}^{k} \sum_{p ε c_{i}}^{k} ∣ p - m_{i} ∣^{2}$ (1) where p is the learner space, M_i is the mean of cluster I, C _i is the centre of cluster I, K is the number of clusters.

Crossover operation combines better parents to produce the best offspring. This crossover operator chooses two parental chromosomes and combine them randomly to produce one or two off-spring. Two-point crossover was applied for this problem, where two random positions were selected for the parent chromosome. Every gene between points was swapped as depicted in Fig. 3.

Fig. 3

Two point crossover.

Mutation Mutation is a significant operator and performance of GA depends on it as it ensures diversity in chromosomes. It completely alters the solution from the previous one and occurs at the rate of probability Pm. It has to be set at low value to prevent GA turning into random search algorithm. Figure 4 depicts mutation operation where three genes are altered.

Fig. 4

Mutation.

The pseudocode for GA k-means is given below in Algorithm 1.

Algorithm 1 Pseudocode for GA k-means

Step 1:

Initialize g to 0;

Initialize Pg to population of size N which is random ;

Step 2:

for 1 to Maxgen

$for each c_{i}^{g} \in P_{g}$

$c_{i}^{*} = K - Means (C_{i});$

$F (C_{i}) = \sum_{i}^{k} \sum_{P \in C_{i}}^{k} | p - m_{i}^{2} |;$

end for each

if Stopping criteria is not satisfied

set P_g toGenerateNewPopp P_g - 1 ;

else

Stop;

Return (C*);

end if

end for

4.3 Phase I: Similarity calculation

Once the alumni were clustered using the GA K-means method, the active learner will be assigned to one of the clusters which matches closely to his profile. If there are many alumni in the cluster say for instance N say 500 alumni, alumni having closer match with active learner (say 100) will be selected by calculating similarity between the active learner and each alumnus. As these calculations are done online when an active learner is using the e-learning system, reducing the number of alumni to an optimal number will reduce the computation time. The algorithm 2 to find the similarity between two learners adopted from Woong and Looi [18] is given as Algorithm 2.

Algorithm 2 Pseudocode for Similarity Calculation

Step 1: Assumption

Useru1 = {C1, E1} andAlumniu2 = {C2, E2}

where Ci is cognitive state, Ei is emotional

state of the user, for i = 1 and i = 2 .

Step 2: Calculate Euclidian distance

D (u1, u2) = ( ∑_{W
_x} (X_c - X_a) ² + W_t (t_c - t_a) ² ) ^-0.5

where X - Learner Attribute

Wx - weight assigned to each learner attribute

(tc-ta) - time difference between current

learner and an alumnus

Wt - - weight associated with time gap

Step 3: Calculate Euclidian distance

$S (c, a) = {\begin{matrix} 1 D = 0 \\ [Log (D)]^{- 0.5} D > 0 \end{matrix}$

4.4 Phase II: Modified ant colony optimization

The basic idea of using ACO is to establish an optimal path for each individual learner to improve his performance. This is done through indirect communication using led pheromone left by other similar learners. The decision on what material to be delivered to a learner at a specific point of time depends on the intensity of the pheromone trail. A learner deposits pheromone along the path he visited, results in increasing the intensity, thus reinforcing the path. The strength of pheromone hints the optimal path.

4.5 Description of modified ant colony algorithm

The working principle of the algorithm is summarized below.

From the starting node, alumni having similar characteristics of the active learner are launched. They act like fully autonomous agents and move forward towards the goal.

Alumni studies learning contents and takes assessment. While moving forward, the time taken to complete the content and marks obtained in the assessment along the path are recorded.

The specific purpose is to find the path that maximizes the performance of the learner.

The learning objects visited by each alumnus is stored to avoid loop.

At each node, the next node to hop is decided based on (i) Pheromone values (ii) Heuristic information.

Once end LO is reached, the pheromone value is updated based on the certain parameters. The information in data structures is also updated.

Once all the needed information is recorded, the alumnus is removed from the path.

In the proposed ACO algorithm, each alumnus builds a feasible solution. The flowchart for the proposed approach is shown in Fig. 5.

Fig. 5

Flowchart of ACO.

4.6 Data structures maintained at each node

The quality of learning path depends on the information stored at the nodes. The data structure at each node is depicted in Fig. 6.

Fig. 6

Data Structures at each node.

Neighbor Node Table: For each node, all connected neighbor nodes (n ε N_k), for choosing the next possible node towards destination node are stored.

Pheromone Table: Store for the pheromone value to all next possible nodes.

Concept Table: The information about concept like difficulty level, prerequisites are stored in each node.

Performance Table: The score obtained by learners traversed through the node is stored.

Time Spent Table: The time spent on the node by each learner and the average time spent by learners is recorded.

The ACO algorithm can be characterized as follows to solve learning path problem:

Initialization: Algorithm parameters are initialized.

Pheromone Computation: The value along the edges called pheromone is computed based on the score obtained by the learner traversed along the path.

Solution Construction: Each alumnus representing ant-like agents starts at starting concept and constructs a solution. The solution constructed by each alumnus will be shared indirectly to others by updating the value of pheromone. The strength pheromone indicates the suitability of the concept. In following iterations, alumni will utilize the strength of the pheromone of available solution. It terminates on satisfying the stopping criterion.

Selection of next suitable material: After the completion of a particular LO, the next LO to be studied will be selected from the neighbour table based on the pheromone values.

Pheromone update: The strength of pheromone is updated based on the solution constructed by active learner. It also includes pheromone evaporation to prevent infinite and unlimited deposition of pheromones.

4.7 Pheromone computation

When a learner traverses along the learning path, he has to take up an assessment activity embedded in the sequence. The scores from the assessment obtained by the learner determines the pheromone intensity. Educational performance at a given location is determined by what has been seen before by the student. Also, the influence decreases with time. Pheromone intensity is calculated using

Results of the formative assessments such as quiz, MCQ, taken at the end of each concept.

Results of the end assessment.

4.8 Selection of next LO

At the intermediate node m, the ant must choose one of the neighbour nodes from neighbour table as next node to visit. The next best node will be recommended to the learner will be based on certain parameters without any preference but, excluding the nodes that ant has already visited. The parameters considered for the selection of next node are:

Pheromone intensity.

Heuristic information.

Information about visited nodes to avoid loop.

4.8.1 Pheromone intensity

Pheromone intensity is the trail left by alumni and is determined by the weights associated with the nodes. The possible outgoing edged from the given node is arranged according to the strength of pheromone. One neighbor node is chosen randomly based on Roulette Wheel selection method. In roulette wheel, the probability of selecting next node is proportional to its fitness value and is given by Equation (2) $τ_{ij} (t) = \frac{f (a_{i})}{\sum_{j \neq i} f (a_{j})}$ (2)

4.8.2 Heuristic information

The heuristic information is determined locally and varies with the nature of the problem is crucial to improve the performance of ACO [30]. Heuristic information η_ij is inversely proportional to the amount time spent to understand the material and defined as $η_{ij} (t) = \frac{1}{1 + \frac{1}{λ S} \ln (1 + λ t_{ij})}$ (3) where t_ij time taken to complete ith material, λ a constant and S is memory power. t_ij calculates the skill to recollect the previous concept after moving to next concept.

4.8.3 Avoid loop

The memory stores the list of visited nodes to avoid choosing the already visited node.

The probability of choosing the next node is given by Equation (4): $P_{ij}^{m} = {\begin{matrix} \frac{[(τ_{ij})^{α}] [(η_{ij})^{β}]}{[(τ_{ij})^{α}] [\sum_{i ε c_{i}^{k}} (η_{ij})^{β}]} if j ε C_{m} \\ 0 otherwise \end{matrix}$ (4) where α,β are parameters. The selection of these parameters is discussed in the evaluation section.

4.9 Pheromone update

Once the alumnus completes the path, the pheromone trails along the path he traversed is updated. It is performed in two steps:

Pheromone evaporation

Trail update

4.9.1 Pheromone evaporation

The pheromone value on the visited nodes are reduced by a constant value in the interval [0,1]. It is decreased as given in Equation (5). $τ_{ij} \leftarrow (1 - ρ) τ_{ij}$ (5)

4.9.2 Trail update

The trail is updated as given in Equation (6). $τ_{ij} = τ_{ij} (t - 1) + \sum_{k = 1}^{m} \nabla τ_{ij}^{k} (t) \forall (ij) ε C$ (6) and $\nabla τ_{ij}^{k} (t)$ is computed as $\nabla τ_{ij}^{k} (t) = η_{ij} + (\frac{{Score}_{ij}^{k}}{{Max}_{score}} \cdot \dot{\frac{1}{{time}_{ij}^{k}}})$ (7)

5 Evaluation of learning path construction using ACO

A experiment was carried out to find the optimal values for ACO parameters which are critical to the performance of the algorithm. A second experiment was conducted to find out the effectiveness of the proposed approach.

5.1 Experiment design - selection of ACO parameters

The ant colony optimization has a large parameter space and these parameters have a vital role in obtaining global optimum and convergence speed. The key parameters of ACO influences the quality of the solution for the given problem Hence, experiments were conducted to determine the value of α, β, ρ, n and to examine the impact of them on behavior of algorithm.

5.1.1 Determine α and β parameter

The coefficient of α influences the pheromone τ_ij (t) to a great extent which in turn determines the path for each ant. The β and ρ parameter are kept constant at 1 and 0.5 respectively. The value of α has varied from 0.5 to 2. The iteration was varied up to 300. The plot of quality of solution Vs Iteration for different values of α is shown in Fig. 7a. The quality of optimal solution used as a measure to determine α value.

Fig. 7

Determination of α and β parameters.

The α and ρ parameters are kept constant at 1 and 0.5 respectively. The value of β is varied from 0.01 to 10. The iteration was set to 300. The quality of solution used as measure to determine β value is shown in Fig. 7b. It is observed that good results were obtained for the medium range of values. The smaller range of values for this parameter was initially bad, but eventually produced the good result after a long time period.

The higher values of both parameters α and β will lead to faster convergence, be able to find the solution quickly. The smaller the value, it gets trapped in the local optimum. It is ascertained from the experiments that suitable values are α ɛ〈 1; 2 〉 and β ɛ〈 2; 3 〉.

5.1.2 Determine number of ants

There is no hard and fast rule to determine right number of ants or iterations. It can be determined by varying the ant count [1, 25, 100, 200, 500] and iteration value was 300.

5.1.3 Determine evaporation parameter

The evaporation factor was varied and was set at 0.1, 0.3, 0.6, 0.75, 1.0. This experiment measured the convergence time of the algorithm for different evaporation factors. The optimal value for the decay constant was chosen at 0.3.

The computation time was determined by the number of ants and the evaporation factor.

The chosen parameters for ACO is shown in Table 3.

Table 3
Parameter setting for ACO

ACO parameters Value

Number of Ants (Alumni) 200

Pheromone Trail Evaporation (ρ) 0.3

Pheromone Parameter (α) 1

Heuristics Parameter (β) 3

Iterations 1000

ACO parameters	Value
Number of Ants (Alumni)	200
Pheromone Trail Evaporation (ρ)	0.3
Pheromone Parameter (α)	1
Heuristics Parameter (β)	3
Iterations	1000

5.2 Experimental design – performance comparison

The effectiveness of the proposed algorithm has been conducted with students with a real course and has been evaluated. The performance of students using proposed approach was compared against the performance of the students using the traditional approach of learning.

5.2.1 Experimental setting and participants

A DBMS course taught to undergraduate students was chosen. The course was divided into 5 concepts. Two topics from each concept was taught. Each topic was covered by a set of learning objects personalized for each individual. They took assessments at the end of each topic and marks are recorded.

The experiment was conducted in two stages.

In the first stage, data required from the alumni were collected. A course on Database Management Systems was developed and around 220 students took the course for 12 weeks. They took assessment at the end of each concept and had a summative assessment after the completion of the course. The marks from assessments were utilised for pheromone computation.

In the second stage, same course was taught to next batch of students. They were split into two cohorts randomly. Both groups undertook pre-test to capture their initial knowledge. The control group followed the traditional learning and the treatment group followed the proposed approach. At the end, both groups attempted same post-test questionnaire.

5.2.2 Evaluating the performance of students

The purpose of the study is to assess the effectiveness of the framework for learners and address through the question

•Does this framework demonstrate a difference in student’s performance?

Analysis of prior knowledge between control and treatment group

A Wilcoxon Signed-Rank test was employed to compare pretest and posttest scores of Treatment and Control group. The specific test was used because the results are not bounded by sample size. As the sample size is small (n<100), this test is considered to be suitable for data analysis. To compare the initial knowledge of both groups Mann-Whitney U test was employed. Considering the smaller sample size and finding out whether or not there is a difference in initial knowledge between two different samples, the chosen test is deemed as appropriate one.

Comparing initial knowledge Table 4 shows the statistics of pre-test scores of treatment and control group. The mean (SD) for the treatment and control group is 28.2(5.65) and 29.8(7.23) respectively.

Table 4
Mean and SD on pre-test scores for treatment and control group

Group Sample Mean SD Max Min

size score score

Treatment Group 40 28.2 5.65 36 22

Control Group 40 29.8 7.23 39 18

Group	Sample	Mean	SD	Max	Min
Treatment Group	40	28.2	5.65	36	22
Control Group	40	29.8	7.23	39	18

The box plots in Fig. 8 shows the distribution of pre-test scores of Control group and Treatment group.

Fig. 8

Box plots of pre-test scores for control and treatment group.

The left box indicates that the pre-test scores of control group were distributed between 20 and 35. The minimum score is 18 and maximum is 39. The right box shows the pre-test scores of treatment group. It reveals that the scores were distributed between 20 and 30. The maximum score is 36 and minimum is 22. The Man-Whitney U test showed that there is no significant difference in the initial between two groups (P = 0.5949).

Comparing Pre-test and Post-test Scores of Treatment group The Wilcoxin Signed Rank test was used to compare pretest and posttest scores. Table 5 shows the mean scores and standard deviation of the treatment and control groups on pre-test and post-test.

Table 5

Mean and SD on pre-test & post-test for treatment and control group

Group	Parameters	Pre-Test	Post-Test
Treatment Group	Mean	28.2	33.5
	Std Deviation	5.65	6.98
Control Group	Mean	29.8	30.8
	Std Deviation	7.23	8.38

P value obtained from the test is 0.0019. The result indicated that here is a significant difference between pre-test and post-test scores. The post-test scores are higher than the pre-test scores. The box plot in Fig. 9 (Treatment Group) shows the distribution of pre-test and post-test scores of the treatment group collectively.

Fig. 9

Comparison of pre-test and post-test scores.

From the plot, it is clear that the posttest performance of the participants is better than pre-test performance. The mean of the pretest (pretest mean = 28.2; Posttest mean =33.5) has increased. The maximum and minimum scores have also increased considerably. It is evident that all individual has gained more scores than the pretest. The graph shows that nearly 70% of the participants have significant difference between their scores. Low performing students (scores < 25) has performed well and shown improvement in their learning. It is significant to note that the post test score for all the students has not fallen below their pre test scores. Every student in the treatment group has shown improvement in their performance.

Comparing Pre-test and Post-test Scores of Control group The Wilcoxin Signed Rank test was used to compare the pre-test and post test scores of control group. The P value (P = 0.1479) obtained from the analysis indicates that there is no significant difference between the pre-test and post-test scores. The performance of two groups of student for all five concepts was compared and is shown in Fig. 10.

Fig. 10

Comparison of performance between control and treatment group.

The box plot graph indicates that there is a small improvement in the overall performance of the students.The box plot is shown in Fig. 9 (Control Group). The maximum mark in the post-test is higher than the pre-test. At the same time, the minimal mark in the post test dropped further. The scatter gram diagram shows the difference between pre-test and post-test scores of all individuals in the treatment group. 40% of the students secured lesser scores than pre-test. Though the remaining 60% of the students got more scores than pre-test, most of them have shown a small improvement in their performance. The result from the Mann-Whitney U test indicated that there is no significant difference in the initial knowledge between two groups. Although there was slight difference in mean pre-test scores between control group (m = 28.2) and treatment group (m = 29.8), the difference was not significant. The analysis of quantitative data of the treatment group indicated that the post-test scores are significantly higher than the pre-test scores. The students showed an improvement in their performance and achievement on the post test scores. The results from the control group data indicated that there is slight improvement in the overall performance of the students. But, the difference in the pre-test and post-test scores is not significantly different.

As observed from the results, there were no significant differences in the initial knowledge for both groups. This indicated that there is no bias while categorizing the participants into one of the groups. The post-test results show that there was a significant difference between the treatment and control groups. The effective size of the impact was medium to large. That means proposed approach had a moderate to large positive impact on the learners’ performance. After investigating the effectiveness of proposed approach against traditional learning approach, it can be observed from the results that overall performance of the students using the proposed approach outperformed the students in the other group.

6 Conclusion

With the advancement of technology, specifically in the field of education, there are more opportunities to provide personalized learning experiences for learners. An adaptive learning environment can provide personalized learning support for learners with different prior knowledge, learning preferences or styles. One way to personalize the learning experience is by recommending a personalized learning path to learners based on their characteristics. In this paper, a modified ant colony optimization algorithm was proposed as a solution to personalized learning path problem. In e-learning system, massive amount of content are available and it is difficult to filter the right content. Secondly, delivering irrelevant or less significant content will make learner frustrated and cause drop in their performance. To overcome this issue, the personalized learning path was recommended according to their emotion and ability.

The proposed approach provided adaptive learning based on the success of the similar alumni learners. The similar alumni learners were grouped based on personalized parameter using GA k-means algorithm. The active learner was assigned to one of the groups based on his similarity level. The alumni of that specific group act like artificial ants and traverse the course network. Parameters of this algorithm were chosen through experiments in order to improve the efficiency. The pheromone values, heuristic information were calculated during the tour and construct the solution. The learner starts the course with a start node. The algorithm chose the next node based on the success level of the node (i.e. the highest score obtained and less time spent) marked as pheromone value. When the learner finishes the tour, the pheromone value is updated. It was decreased by constant evaporation factor. Then value was increased proportional to the score obtained and inversely proportional to the time spent on that node. The result of the experiments showed that the treatment group had a higher performance and improvement in the course than the control group. The performance difference between the two groups was significant based on the statistical test. It is evident that the learning path constructed based on the proposed approach has improved their performance.

This study can be extended to reduce the time needed to present the personalized learning path. With the higher number of iterations and alumni, the computational intensity increases, an effective way is to parallel the search using recent advances in parallel programming and hardware architecture.

References

Chen

Chih-Ming

, Intelligent web-based learning system with personalized learning path guidance, Computers and Education 51(2) (2008), 787–814.

Bennane

Abdellah

, Adaptive educational software by applying reinforcement learning, Informatics in Education 12(1) (2013).

Hao

, Song

Donglei

, Yu

Tao

and Tavares

Adriano

, An enjoyable learning experience in personalising learning based on knowledge management: A case study, Eurasia J Math Sci Technol Educ 13 (2017), 3001–3018.

Béres

Ilona

, Magyar

Timea

and Turcsányi-Szabó

Márta

, Towards a personalised, learning style based collaborative blended learning model with individual assessment, Informatics in Education 11(1) (2012), 1–28.

Alian

Marwah

and Jabri

Riad

, A shortest adaptive learning path in elearning systems: mathematical view, Journal of American Science 5(6) (2009), 32–42.

Brusilovsky

, Adaptive hypermedia, user modeling and user adapted interaction, Ten Year Anniversary 11 (2001), 1–2.

Brusilovsky

Peter

, et al. Adaptive educational systems on the world-wide-web: A review of available technologies. In Proceedings of Workshop” WWW-Based Tutoring” at 4th International Conference on Intelligent Tutoring Systems (ITS’98), San Antonio, TX, 1998.

Brusilovsky

Peter

, Adaptive navigation support. In The adaptive web, pages 263–290. Springer, 2007.

Boyle

Craig

and Encarnacion

Antonio O

, Metadoc: an adaptive hypertext reading system. In Adaptive Hypertext and Hypermedia, pages 71–89. Springer, 1998.

10.

Yang

Fan

, Frederick

WB Li

and Rynson

WH Lau

, An open model for learning path construction. In International Conference on Web-Based Learning, pages 318–328. Springer, 2010.

11.

Kurilovas

Eugenijus

, Zilinskiene

Inga

and Dagiene

Valentina

, Recommending suitable learning scenarios according to learners’ preferences: An improved swarm based approach, Computers in Human Behavior 30 (2014), 550–557.

12.

Tattersall

Colin

, Manderveld

Jocelyn

, Van den Berg

Bert

, Van Es

René

, Janssen

José

and Koper

Rob

, Self organising wayfinding support for lifelong learners, Education and Information technologies 10(1-2) (2005), 111–123.

13.

Acampora

Giovanni

, Gaeta

Matteo

and Loia

Vincenzo

, Hierarchical optimization of personalized experiences for elearning systems through evolutionary models, Neural Computing and Applications 20(5) (2011), 641–657.

14.

Semet

Yann

, Lutton

Evelyne

and Collet

Pierre

, Ant colony optimisation for e-learning: Observing the emergence of pedagogic suggestions. In Swarm Intelligence Symposium, 2003. SIS’03. Proceedings of the 2003 IEEE, pages 46–52. IEEE, 2003.

15.

Valigiani

Grégory

, Biojout

Raphael

, Jamont

Yannick

, Lutton

Evelyne

, Collet

, et al. Experimenting with a real-size manhill to optimize pedagogical paths. In Proceedings of the 2005 ACM symposium on Applied computing, pages 4–8. ACM, 2005.

16.

Gutiérrez

Sergio

, Valigiani

Grégory

, Collet

Pierre

and Delgado Kloos

Carlos

, Adaptation of the aco heuristic for sequencing learning activities. In Proceedings of the EC-TEL, pages 17–20, 2007.

17.

Wang

Tzone-I

, Wang

Kun-Te

and Huang

Yueh-Min

, Using a style-based ant colony system for adaptive learning, Expert Systems with applications 34(4) (2008), 2449–2464.

18.

Wong

Lung-Hsiang

and Looi

Chee-Kit

, Adaptable learning pathway generation with ant colony optimization, Journal of Educational Technology & Society 12(3) (2009).

19.

Kardan

Ahmad A.

, Ale Ebrahim

Molood

and Bahojb Imani

Maryam

, A new personalized learning path generation method: Aco-map, Indian Journal of Scientific Research 5(1) (2014), 17.

20.

Zhao

Chengling

and Wan

Liyong

, A shortest learning path selection algorithm in e-learning. In Advanced Learning Technologies, 2006. Sixth International Conference on, pages 94–95. IEEE, 2006.

21.

Seki

Kazuya

, Matsui

Tatsunori

and Okamoto

Toshio

, An adaptive sequencing method of the learning objects for the e-learning environment, Electronics and Communications in Japan (Part III: Fundamental Electronic Science) 88(3) (2005), 54–71.

22.

Hovakimyan

Anna

, Sargsyan

Siranush

and Barkhoudaryan

Sergey

, Genetic algorithm and the problem of getting knowledge in e-learning systems. In Advanced Learning Technologies, 2004. Proceedings. IEEE International Conference on, pages 336–339. IEEE, 2004.

23.

Samia

Azough

and Mostafa

Bellafkih

, Re-use of resources for adapted formation to the learner. In Computational Intelligence and Intelligent Informatics, 2007. ISCIII’07. International Symposium on, pages 213–217. IEEE, 2007.

24.

Huang

Mu-Jung

, Huang

Hwa-Shan

and Chen

Mu-Yen

, Constructing a personalized e-learning system based on genetic algorithm and case-based reasoning approach, Expert Systems with Applications 33(3) (2007), 551–564.

25.

Dwivedi

Pragya

, Kant

Vibhor

and Bharadwaj

Kamal K

, Learning path recommendation based on modified variable length genetic algorithm, Education and Information Technologies 23(2) (2018), 819–106.

26.

Wan

Shanshan

and Niu

Zhendong

, A learner oriented learning recommendation approach based on mixed concept mapping and immune algorithm, Knowledge-Based Systems 103 (2016), 28–40.

27.

Vanitha

, Krishnan

and Elakkiya

, Collaborative optimization algorithm for learning path construction in e-learning, Computers & Electrical Engineering 77 (2019), 325–338.

28.

Vanitha

and Krishnan

, Time-frequency analysis of eeg for improved classification of emotion, International Journal of Biomedical Engineering and Technology 23(2/3) (2017), 4.

29.

Kim

Kyoung-jae

and Ahn

Hyunchul

, A recommender system using ga k-means clustering in an online shopping market, Expert systems with applications 34(2) (2008), 1200–1209.

30.

Dorigo

Marco

, Optimization, Learning and Natural Algorithms. PhD Thesis, Politecnico di Milano, 1992.

Learner	Learner Characteristics
	Anger	Anxiety	Boredom	Frustration	Eureka	Curious	WMC	Load
	Present(1) /Absent (0)						High(1) / Low(0)
Learner 1	1	0	0	0	0	0	1	1
Learner 2	0	0	0	0	1	0	0	1
Learner 3	0	0	0	1	0	0	0	0

A modified ant colony algorithm for personalized learning path construction

Abstract

Keywords

1 Introduction

2 Review on approaches to learning path construction

3 Stigmergy model description

3.1 Problem formulation

3.3 Description of learner model

3.4 Description of learning content model

4 Methodology for learning path construction

4.1 Proposed stigmergy model

4.2.1 Phase I: Learner Characteristics

Table 2 Learner characteristics representation Learner Learner Characteristics Anger Anxiety Boredom Frustration Eureka Curious WMC Load Present(1) /Absent (0) High(1) / Low(0) Learner 1 1 0 0 0 0 0 1 1 Learner 2 0 0 0 0 1 0 0 1 Learner 3 0 0 0 1 0 0 0 0

4.4 Phase II: Modified ant colony optimization

4.5 Description of modified ant colony algorithm

4.8 Selection of next LO

4.8.1 Pheromone intensity

4.9.1 Pheromone evaporation

5.1 Experiment design - selection of ACO parameters

5.1.1 Determine α and β parameter

5.1.3 Determine evaporation parameter

Table 3 Parameter setting for ACO ACO parameters Value Number of Ants (Alumni) 200 Pheromone Trail Evaporation (ρ) 0.3 Pheromone Parameter (α) 1 Heuristics Parameter (β) 3 Iterations 1000

5.2.1 Experimental setting and participants

5.2.2 Evaluating the performance of students

Table 4 Mean and SD on pre-test scores for treatment and control group Group Sample Mean SD Max Min size score score Treatment Group 40 28.2 5.65 36 22 Control Group 40 29.8 7.23 39 18

References

Table 2
Learner characteristics representation

Learner Learner Characteristics

Anger Anxiety Boredom Frustration Eureka Curious WMC Load

Present(1) /Absent (0) High(1) / Low(0)

Learner 1 1 0 0 0 0 0 1 1

Learner 2 0 0 0 0 1 0 0 1

Learner 3 0 0 0 1 0 0 0 0

Table 3
Parameter setting for ACO

ACO parameters Value

Number of Ants (Alumni) 200

Pheromone Trail Evaporation (ρ) 0.3

Pheromone Parameter (α) 1

Heuristics Parameter (β) 3

Iterations 1000

Table 4
Mean and SD on pre-test scores for treatment and control group

Group Sample Mean SD Max Min

size score score

Treatment Group 40 28.2 5.65 36 22

Control Group 40 29.8 7.23 39 18